Back to Search
Start Over
Efficient Exact Enumeration of Single-Source Geodesics on a Non-Convex Polyhedron.
- Source :
-
International Journal of Computational Geometry & Applications . Sep-Dec2023, Vol. 33 Issue 3/4, p97-132. 36p. - Publication Year :
- 2023
-
Abstract
- In this paper, we consider enumeration of geodesics on a polyhedron, where a geodesic means locally-shortest path between two points. Particularly, we consider the following preprocessing problem: given a point s on a polyhedral surface and a positive real number r , to build a data structure that enables, for any point t on the surface, to enumerate all geodesics from s to t whose length is less than r. First, we present a naive algorithm by removing the trimming process from the MMP algorithm (1987). Next, we present an improved algorithm which is practically more efficient on a non-convex polyhedron, in terms of preprocessing time and memory consumption. Moreover, we introduce a single-pair geodesic graph to succinctly encode a result of geodesic query. Lastly, we compare these naive and improved algorithms by some computer experiments. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYHEDRA
*DATA structures
*REAL numbers
*GEODESICS
*COMPUTER algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 33
- Issue :
- 3/4
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 174622333
- Full Text :
- https://doi.org/10.1142/S0218195923500048