Space complexity of exact discrete geodesic algorithms on regular triangulations. (English) Zbl 1409.68307
Summary: Computing geodesic distances on 2-manifold meshes is a fundamental problem in computational geometry. To date, two notable classes of exact algorithms, namely, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been widely studied. For an arbitrary triangle mesh with \(n\) vertices, these algorithms have space complexity of \(O(n^2)\). In this paper, we prove that both algorithms have \(\Theta(n^{1.5})\) space complexity on a completely regular triangulation (i.e., all triangles are equilateral).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Mitchell, J.; Mount, D.; Papadimitriou, C., The discrete geodesic problem, SIAM J. Comput., 16, 4, 647-668 (1987) · Zbl 0625.68051 |
| [2] | Chen, J.; Han, Y., Shortest paths on a polyhedron, (Proc. 6th Annual Symposium on Computational Geometry. Proc. 6th Annual Symposium on Computational Geometry, SCG’90 (1990)), 360-369 |
| [3] | Liu, Y.-J., Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures, Comput. Aided Des., 45, 3, 695-704 (2013) |
| [4] | Xu, C.-X.; Wang, T. Y.; Liu, Y.-J.; Liu, L.; He, Y., Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes, IEEE Trans. Vis. Comput. Graph., 21, 7, 822-834 (2015) |
| [5] | Kimmel, R.; Sethian, J., Computing geodesic paths on manifolds, PNAS, 95, 15, 8431-8435 (1998) · Zbl 0908.65049 |
| [6] | Surazhsky, V.; Surazhsky, T.; Kirsanov, D.; Gortler, S.; Hoppe, H., Fast exact and approximate geodesics on meshes, ACM Trans. Graph., 24, 3, 553-560 (2005) |
| [7] | Sandor, J.; Mitrinovic, D.; Crstici, B., Handbook of Number Theory I (2006), Springer · Zbl 1151.11300 |
| [8] | Moet, E.; van Kreveld, M.; van der Stappen, A. F., On realistic terrains, Comput. Geom. Theory Appl., 41, 1-2, 48-67 (2008) · Zbl 1152.65034 |
| [9] | de Berg, M.; Katz, M.; van der Stappen, A. F.; Vleugels, J., Realistic input models for geometric algorithms, Algorithmica, 34, 1, 81-97 (2002) · Zbl 1017.68141 |
| [10] | Liu, Y.-J.; Chen, Z.; Tang, K., Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces, IEEE Trans. Pattern Anal. Mach. Intell., 33, 8, 1502-1517 (2011) |
| [11] | Liu, Y.-J., Semi-continuity of skeletons in two-manifold and discrete Voronoi approximation, IEEE Trans. Pattern Anal. Mach. Intell., 37, 9, 1938-1944 (2015) |
| [12] | Liu, Y.-J.; Xu, C.-X.; Yi, R.; Fan, D.; He, Y., Manifold differential evolution (MDE): a global optimization method for geodesic centroidal Voronoi tessellations on meshes, ACM Trans. Graph., 35, 6, 243:1-243:10 (2016) |
| [13] | Liu, Y.-J.; Fan, D.; Xu, C.-X.; He, Y., Constructing intrinsic Delaunay triangulations from the dual of geodesic Voronoi diagrams, ACM Trans. Graph., 36, 2, 15:1-15:15 (2017) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
