Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorWang, Xiaoningen
dc.contributor.authorFang, Zhengen
dc.contributor.authorWu, Jiajunen
dc.contributor.authorXin, Shi-Qingen
dc.contributor.authorHe, Yingen
dc.identifier.citationWang, X., Fang, Z., Wu, J., Xin, S.-Q., & He, Y. (2017). Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces. Computer Aided Geometric Design, 52-53, 262-284.en
dc.description.abstractWe present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and ε>0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show that the DGG associated to M has O(n/sqrt(ε)) edges and the shortest path distances on the graph approximate geodesic distances on M with relative error O(ε). Computational results show that the actual error is less than 0.6ε on common models. Taking advantage of DGG's unique features, we develop a DGG-tailored label-correcting algorithm that computes geodesic distances in empirically linear time. With DGG, we can guarantee the computed distances are true distance metrics, which is highly desired in many applications. We observe that DGG significantly outperforms saddle vertex graph (SVG) – another graph based method for discrete geodesics – in terms of graph size, accuracy control and runtime performance.en
dc.description.sponsorshipMOE (Min. of Education, S’pore)en
dc.format.extent19 p.en
dc.relation.ispartofseriesComputer Aided Geometric Designen
dc.rights© 2017 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by Computer Aided Geometric Design, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [].en
dc.subjectGeodesic Distancesen
dc.subjectPolyhedral Surfacesen
dc.titleDiscrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfacesen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Computer Science and Engineeringen
dc.description.versionAccepted versionen
item.fulltextWith Fulltext-
Appears in Collections:SCSE Journal Articles
Files in This Item:
File Description SizeFormat 
Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces.pdf9.65 MBAdobe PDFThumbnail

Citations 20

Updated on Jan 23, 2023

Web of ScienceTM
Citations 20

Updated on Jan 22, 2023

Page view(s) 20

Updated on Jan 27, 2023

Download(s) 10

Updated on Jan 27, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.