A Fast Sweeping Method for Computing Geodesics on Triangular Manifolds

Abstract : A wide range of applications in computer intelligence and computer graphics require computing geodesics accurately and efficiently. The fast marching method (FMM) is widely used to solve this problem, of which the complexity is OðN logNÞ, where N is the total number of nodes on the manifold. A fast sweeping method (FSM) is proposed and applied on arbitrary triangular manifolds of which the complexity is reduced to OðNÞ. By traversing the undigraph, four orderings are built to produce two groups of interfering waves, which cover all directions of characteristics. The correctness of this method is proved by analyzing the coverage of characteristics. The convergence and error estimation are also presented.
Type de document :
Article dans une revue
IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2010
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00517321
Contributeur : Thss Tsinghua <>
Soumis le : mardi 14 septembre 2010 - 10:50:26
Dernière modification le : mardi 14 septembre 2010 - 11:53:14
Document(s) archivé(s) le : mercredi 15 décembre 2010 - 02:40:27

Fichier

Song-Gang_Xu2010a.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00517321, version 1

Citation

Song-Gang Xu, Yun-Xiang Zhang, Jun-Hai Yong. A Fast Sweeping Method for Computing Geodesics on Triangular Manifolds. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2010. 〈inria-00517321〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

186