The Discrete Geodesic Problem
The DOI matches its Crossref record; 10 of the 12 references it cites were found in a registry or an index, and 2 are not checked yet.
Abstract
We present an algorithm for determining the shortest path between a source and a destination on an arbitrary (possibly nonconvex) polyhedral surface. The path is constrained to lie on the surface, and distances are measured according to the Euclidean metric. Our algorithm runs in time $O(n^2 \log n)$ and requires $O(n^2 )$ space, where n is the number of edges of the surface. After we run our algorithm, the distance from the source to any other destination may be determined using standard techniques in time $O(\log n)$ by locating the destination in the subdivision created by the algorithm. The actual shortest path from the source to a destination can be reported in time $O(k + \log n)$, where k is the number of faces crossed by the path. The algorithm generalizes to the case of multiple source points to build the Voronoi diagram on the surface, where n is now the maximum of the number of vertices and the number of sources.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
An algorithm for planning collision-free paths among polyhedral obstacles
Lozano-Pérez, T., & Wesley, M. A. (1979) · Communications of the ACM · doi:10.1145/359156.359164 · Cited by 2,304
Optimal Search in Planar Subdivisions
Kirkpatrick, D. (1983) · SIAM Journal on Computing · doi:10.1137/0212002 · Cited by 739
Euclidean shortest paths in the presence of rectilinear barriers
Lee, D. T., & Preparata, F. P. (1984) · Networks · doi:10.1002/net.3230140304 · Cited by 387
On Shortest Paths in Polyhedral Spaces
Sharir, M., & Schorr, A. (1986) · SIAM Journal on Computing · doi:10.1137/0215014 · Cited by 313
Triangulating a simple polygon
Garey, M. R., Johnson, D. S., Preparata, F. P., & Tarjan, R. E. (1978) · Information Processing Letters · doi:10.1016/0020-0190(78)90062-5 · Cited by 296
An algorithm for shortest-path motion in three dimensions
Papadimitriou, C. H. (1985) · Information Processing Letters · doi:10.1016/0020-0190(85)90029-8 · Cited by 192
Self-citationA New Approach to Planar Point Location
Preparata, F. P. (1981) · SIAM Journal on Computing · doi:10.1137/0210035 · Cited by 127
Shortest paths on polyhedral surfaces
O’Rourke, J., Suri, S., & Booth, H. D. (2005) · Springer eBooks · doi:10.1007/bfb0024013 · Cited by 48
Voronoi Diagrams on the Surface of a Polyhedron.
Mount, D. M. (1985) · Defense Technical Information Center (DTIC) · doi:10.21236/ada166220 · Cited by 40
Self-citation3-dimensional shortest paths in the presence of polyhedral obstacles
Reif, J. H., & Storer, J. A. (2005) · Springer eBooks · doi:10.1007/bfb0017133 · Cited by 19
Shortest paths : variational problems
Li︠u︡sternik, L. A., Collins, P., & Brown, R. B. (1964) · Medical Entomology and Zoology · Cited by 14
Research works printed but not linked: 4
- D. T. Lee, Proximity and reachability in the plane, Ph.D. thesis, Technical Report, ACT-12, Coordinated Science Laboratory, Univ. of Illinois, Chicago, IL, 1978, November
- J. S. B. Mitchell, Ph.D. Thesis, Planning shortest paths, Dept. of Operations Research, Stanford Univ., Stanford, CA, 1986, August, (Available as Research Report 561, Artificial Intelligence Series, No. 1, Hughes Research Laboratories, Malibu, CA.) 0755.90084
- D. M. Mount, On finding shortest paths on convex polyhedra, Technical Report, 1495, Dept. of Computer Science, Univ. of Maryland, Baltimore, MD, 1985 · doi:10.21236/ada166246
- D. M. Mount, Storing the subdivision of a polyhedral surface, Proc. 2nd ACM Symposium on Computational Geometry, Yorktown Heights, NY, 1986, June 2–4 0615.52008
Cited by
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
Situating the default-mode network along a principal gradient of macroscale cortical organization
Margulies, D. S., Ghosh, S. S., Goulas, A., Falkiewicz, M., Huntenburg, J. M., Langs, G., Bezgin, G., Eickhoff, S. B., Castellanos, F. X., Petrides, M., et al. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1608282113 · Cited by 2,321
Topology matching for fully automatic similarity estimation of 3D shapes
Hilaga, M., Shinagawa, Y., Kohmura, T., & Kunii, T. L. (2001) · Proceedings of the 28th annual conference on Computer graphics and interactive techniques · doi:10.1145/383259.383282 · Cited by 2,187
Multiresolution analysis of arbitrary meshes
Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., & Stuetzle, W. (1995) · Proceedings of the 22nd annual conference on Computer graphics and interactive techniques - SIGGRAPH '95 · doi:10.1145/218380.218440 · Cited by 1,205
Davenport-Schinzel Sequences and their Geometric Applications
Sharir, M. (1988) · Springer eBooks · doi:10.1007/978-3-642-83539-1_9 · Cited by 891
Metadata
- Authors
- Mitchell, J. S. B., Mount, D. M., & Papadimitriou, C. H.
- Affiliations
- Stanford University (US)
- University of Maryland, Baltimore (US)
- Venue
- SIAM Journal on Computing
- Published
- 1987-08
- Volume
- 16
- Issue
- 4
- Pages
- 647-668
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2108567935
- Cited by
- 720
- References
- 11
- Citations by year
- 2026: 17 · 2025: 25 · 2024: 28 · 2023: 39 · 2022: 22 · 2021: 27 · 2020: 25 · 2019: 29 · 2018: 24 · 2017: 26 · 2016: 25 · 2015: 35 · 2014: 34 · 2013: 31 · 2012: 26
- FWCI
- 12.77
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computational Geometry and Mesh Generation
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Keywords
- non-convex polyhedra, Euclidean distance, shortest path algorithms, computational geometry
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.