Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/inria-00517321
Contributor : Thss Tsinghua <>
Submitted on : Tuesday, September 14, 2010 - 10:50:26 AM
Last modification on : Tuesday, September 14, 2010 - 11:53:14 AM
Long-term archiving on: : Wednesday, December 15, 2010 - 2:40:27 AM

File

Song-Gang_Xu2010a.pdf
Publisher files allowed on an open archive

Identifiers

  • 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⟩

Share

Metrics

Record views

193

Files downloads

239