{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T17:47:51Z","timestamp":1792086471684,"version":"4.4.0"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1987,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/0216045","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:28:18Z","timestamp":1109226498000},"page":"647-668","source":"Crossref","is-referenced-by-count":552,"title":["The Discrete Geodesic Problem"],"prefix":"10.1137","volume":"16","author":[{"given":"Joseph S. B.","family":"Mitchell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"R4","unstructured":"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"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"R7","volume-title":"Shortest paths. Variational problems","author":"Lyusternik L. A.","year":"1964"},{"key":"R8","unstructured":"J. S. B. Mitchell,  Shortest paths in the plane in the presence of obstacles,  1984, Manuscript, Dept. of Operations Research, Stanford Univ., Stanford, CA"},{"key":"R9","unstructured":"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"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"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"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"D. M. Mount,  Voronoi diagrams on the surface of a polyhedron, Technical Report, 1496, Dept. of Computer Science, Univ. of Maryland, Baltimore, MD,  1985","DOI":"10.21236\/ADA166220"},{"key":"R12","unstructured":"D. M. Mount,  Storing the subdivision of a polyhedral surface,  Proc. 2nd ACM Symposium on Computational Geometry, Yorktown Heights, NY,  1986, June 2\u20134 0615.52008"},{"key":"R13","unstructured":"J. O'Rourke, S. Suri, H. Booth,  Shortest paths on polyhedral surfaces,  1984, Manuscript, The Johns Hopkins Univ., Baltimore, MD"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90029-8"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0210035"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. H. Reif, J. A. Storer,  Shortest paths in Euclidean space with polyhedral obstacles, Technical Report, CS-85-121, Computer Science Dept., Brandeis Univ., Waltham, MA,  1985, April","DOI":"10.1007\/BFb0017133"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0216045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:45:29Z","timestamp":1787337929000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0216045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,8]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,8]]}},"alternative-id":["10.1137\/0216045"],"URL":"https:\/\/doi.org\/10.1137\/0216045","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,8]]}}}