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-citation
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
Gross motion planning—a survey
Hwang, Y. K., & Ahuja, N. (1992) · ACM Computing Surveys · doi:10.1145/136035.136037 · Cited by 826
Fast exact and approximate geodesics on meshes
Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., & Hoppe, H. (2005) · ACM Transactions on Graphics · doi:10.1145/1073204.1073228 · Cited by 502
Papadimitriou, C. H., & Yannakakis, M. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90263-2 · Cited by 490
Self-citationFitting smooth surfaces to dense polygon meshes
Krishnamurthy, V., & Levoy, M. (1996) · Proceedings of the 23rd annual conference on Computer graphics and interactive techniques · doi:10.1145/237170.237270 · Cited by 474
Kröger, M. (2005) · Computer Physics Communications · doi:10.1016/j.cpc.2005.01.020 · Cited by 459
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Self-citationVoronoi Diagrams**Partially supported by the Deutsche Forschungsgemeinschaft, grant K1 655 2-2.
Aurenhammer, F., & Klein, R. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50006-1 · Cited by 392
An Optimal Algorithm for Euclidean Shortest Paths in the Plane
Hershberger, J. E., & Suri, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539795289604 · Cited by 374
Shortest paths on a polyhedron
Chen, J., & Han, Y. (1990) · Proceedings of the sixth annual symposium on Computational geometry - SCG '90 · doi:10.1145/98524.98601 · Cited by 301
Geodesics in heat: A new approach to computing distance based on heat flow
Crane, K., Weischedel, C., & Wardetzky, M. (2013) · ACM Transactions on Graphics · doi:10.1145/2516971.2516977 · Cited by 297
The weighted region problem: finding shortest paths through a weighted planar subdivision
Mitchell, J. S. B., & Papadimitriou, C. H. (1991) · Journal of the ACM · doi:10.1145/102782.102784 · Cited by 295
Self-citationThe heat method for distance computation
Crane, K., Weischedel, C., & Wardetzky, M. (2017) · Communications of the ACM · doi:10.1145/3131280 · Cited by 259
Planar graphs, negative weight edges, shortest paths, and near linear time
Fakcharoenphol, J., & Rao, S. B. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2005.05.007 · Cited by 255
Greedy optimal homotopy and homology generators
Erickson, J., & Whittlesey, K. (2005) · doi:10.5555/1070432.1070581 · Cited by 208
A Fast Iterative Method for Eikonal Equations
Jeong, W., & Whitaker, R. (2008) · SIAM Journal on Scientific Computing · doi:10.1137/060670298 · Cited by 199
Sampling-Based Methods for Motion Planning with Constraints
Kingston, Z., Moll, M., & Kavraki, L. E. (2018) · Annual Review of Control, Robotics, and Autonomous Systems · doi:10.1146/annurev-control-060117-105226 · Cited by 193
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-citationGeodesic Methods in Computer Vision and Graphics
Peyré, G., Péchaud, M., Keriven, R., & Cohen, L. D. (2009) · now publishers, Inc. eBooks · doi:10.1561/0600000029 · Cited by 188
Improving Chen and Han's algorithm on the discrete geodesic problem
Xin, S., & Wang, G. (2009) · ACM Transactions on Graphics · doi:10.1145/1559755.1559761 · Cited by 180
Optimally Cutting a Surface into a Disk
Erickson, J., & Har-Peled, S. (2003) · Discrete & Computational Geometry · doi:10.1007/s00454-003-2948-z · Cited by 175
A numerical solution to the generalized mapmaker's problem: flattening nonconvex polyhedral surfaces
Schwartz, E. L., Shaw, A., & Wolfson, E. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.35506 · Cited by 172
Representation and Spatial Analysis in Geographic Information Systems
Miller, H. J., & Wentz, E. A. (2003) · Annals of the Association of American Geographers · doi:10.1111/1467-8306.9303004 · Cited by 165
Efrat, A., Fan, Q., & Venkatasubramanian, S. (2007) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-006-0647-0 · Cited by 161
Exploring implicit spaces for constrained sampling-based planning
Kingston, Z. K., Moll, M., & Kavraki, L. E. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364919868530 · Cited by 157
A survey of motion planning and related geometric algorithms
Schwartz, J. T., & Sharir, M. (1988) · Artificial Intelligence · doi:10.1016/0004-3702(88)90053-7 · Cited by 157
A Field-Based Theory for Time Geography
Miller, H. J., & Bridwell, S. A. (2009) · Annals of the Association of American Geographers · doi:10.1080/00045600802471049 · Cited by 155
MemBrain v2: an end-to-end tool for the analysis of membranes in cryo-electron tomography
Lamm, L., Zufferey, S., Zhang, H., Righetto, R. D., Waltz, F., Wietrzyñski, W., Yamauchi, K. A., Burt, A., Liu, Y., Martínez-Sánchez, A., et al. (2026) · Nature Methods · doi:10.1038/s41592-026-03178-8 · Cited by 152
Δ -PINNs: Physics-informed neural networks on complex geometries
Costabal, F. S., Pezzuto, S., & Perdikaris, P. G. (2023) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2023.107324 · Cited by 152
Extracting skeletal curves from 3D scattered data
Verroust-Blondet, A., & Lazarus, F. (1999) · IEEE International Conference on Shape Modeling and Applications · doi:10.1109/sma.1999.749340 · Cited by 148
Parallel algorithms for approximation of distance maps on parametric surfaces
Weber, O., Devir, Y. S., Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2008) · ACM Transactions on Graphics · doi:10.1145/1409625.1409626 · Cited by 147
Bringing clothing into desired configurations with limited perception
Cusumano-Towner, M., Singh, A., Miller, S., O'Brien, J. F., & Abbeel, P. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5980327 · Cited by 146
Earth mover's distances on discrete surfaces
Solomon, J., Rustamov, R. M., Guibas, L. J., & Butscher, A. (2014) · ACM Transactions on Graphics · doi:10.1145/2601097.2601175 · Cited by 146
L 1 shortest paths among polygonal obstacles in the plane
Mitchell, J. S. B. (1992) · Algorithmica · doi:10.1007/bf01758836 · Cited by 145
Self-citationApproximating weighted shortest paths on polyhedral surfaces
Lanthier, M. A., Maheshwari, A., & Sack, J.-R. (1997) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/262839.262984 · Cited by 143
Sharp, N., Soliman, Y., & Crane, K. (2019) · ACM Transactions on Graphics · doi:10.1145/3243651 · Cited by 142
Level set diagrams of polyhedral objects
Lazarus, F., & Verroust-Blondet, A. (1999) · ACM Symposium on Solid Modeling and Applications · doi:10.1145/304012.304025 · Cited by 141
An algorithmic approach to some problems in terrain navigation
Mitchell, J. S. B. (1988) · Artificial Intelligence · doi:10.1016/0004-3702(88)90054-9 · Cited by 139
Self-citationAlgorithmic motion planning in robotics
Sharir, M. (1989) · Computer · doi:10.1109/2.16221 · Cited by 138
Nash, A., & Koenig, S. (2013) · AI Magazine · doi:10.1609/aimag.v34i4.2512 · Cited by 137
Shortest paths without a map: Extended abstract
Papadimitriou, C. H., & Yannakakis, M. (1989) · Lecture notes in computer science · doi:10.1007/bfb0035787 · Cited by 137
Self-citationNormal Vector Voting: Crease Detection and Curvature Estimation on Large, Noisy Meshes
Page, D. L., Sun, Y., Koschan, A. F., Paik, J., & Abidi, M. A. (2002) · Graphical Models · doi:10.1006/gmod.2002.0574 · Cited by 137
Discrete differential geometry : An applied introduction
Grinspun, E. (2008) · International Conference on Computer Graphics and Interactive Techniques · Cited by 137
Straightest geodesics on polyhedral surfaces
Polthier, K., & Schmies, M. (2006) · ACM SIGGRAPH Conference (SIGGRAPH) · doi:10.1145/1185657.1185664 · Cited by 130
SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
Chen, J., & Han, Y. (1996) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195996000095 · Cited by 128
Efficient query processing on spatial networks
Sankaranarayanan, J., Alborzi, H., & Samet, H. (2005) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1097064.1097093 · Cited by 125
Efficient computation of geodesic shortest paths
Kapoor, S. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301449 · Cited by 122
Model order reduction assisted by deep neural networks (ROM-net)
Daniel, T., Casenave, F., Akkari, N., & Ryckelynck, D. (2020) · Advanced Modeling and Simulation in Engineering Sciences · doi:10.1186/s40323-020-00153-6 · Cited by 121
Determining approximate shortest paths on weighted polyhedral surfaces
Aleksandrov, L., Maheshwari, A., & Sack, J.-R. (2005) · Journal of the ACM · doi:10.1145/1044731.1044733 · Cited by 121
Pedersen, H. K. (1995) · ACM SIGGRAPH Conference (SIGGRAPH) · doi:10.1145/218380.218458 · Cited by 119
Research Article: Extensions to least-cost path algorithms for roadway planning
YU, C., LEE, J., & MUNRO-STASIUK, M. J. (2003) · International Journal of Geographical Information Science · doi:10.1080/1365881031000072645 · Cited by 118
Weiler, M., Forré, P. D., Verlinde, E., & Welling, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.06020 · Cited by 116
Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated Surfaces
Liu, Y., Chen, Z., & Tang, K. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.221 · Cited by 115
Computing geodesics on triangular meshes
Martínez, D., Velho, L. C. P. R., & Carvalho, P. C. P. (2005) · Computers & Graphics · doi:10.1016/j.cag.2005.08.003 · Cited by 114
Fast exact and approximate geodesics on meshes
Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., & Hoppe, H. (2005) · ACM SIGGRAPH Conference (SIGGRAPH) · doi:10.1145/1186822.1073228 · Cited by 114
Data-driven shape analysis and processing
Xu, K., Kim, V. G., Huang, Q., Mitra, N. J., & Kalogerakis, E. (2016) · SIGGRAPH Asia Courses · doi:10.1145/2988458.2988473 · Cited by 113
Extracting skeletal curves from 3D scattered data
Verroust-Blondet, A., & Lazarus, F. (2000) · The Visual Computer · doi:10.1007/pl00007210 · Cited by 112
Applications of Optimal Multiprocesses
Clarke, F. H., & Vinter, R. (1989) · SIAM Journal on Control and Optimization · doi:10.1137/0327056 · Cited by 111
Spherical and Hyperbolic Embeddings of Data
Wilson, R. C., Hancock, E. R., Pekalska, E., & Duin, R. P. W. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2316836 · Cited by 109
Curved layer based process planning for multi-axis volume printing of freeform parts
Xu, K., Li, Y., Chen, L., & Tang, K. (2019) · Computer-Aided Design · doi:10.1016/j.cad.2019.05.007 · Cited by 104
Metamorphosis of arbitrary triangular meshes
Kanai, T., Suzuki, H., & KIMURA, F. (2000) · IEEE Computer Graphics and Applications · doi:10.1109/38.824544 · Cited by 104
Star Unfolding of a Polytope with Applications
Agarwal, P. K., Aronov, B. S., O’Rourke, J., & Schevon, C. A. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539793253371 · Cited by 103
A Survey of Algorithms for Geodesic Paths and DistancesPreprint
Crane, K., Livesu, M., Puppo, E., & Qin, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.10430 · Cited by 102
On the Optimality of Shape and Data Representation in the Spectral Domain
Aflalo, Y., Brézis, H., & Kimmel, R. (2015) · SIAM Journal on Imaging Sciences · doi:10.1137/140977680 · Cited by 101
Applications of Computational Geometry to Geographic Information Systems
Floriani, L. D., Magillo, P., & Puppo, E. (2000) · Elsevier eBooks · doi:10.1016/b978-044482537-7/50008-5 · Cited by 101
You can find geodesic paths in triangle meshes by just flipping edges
Sharp, N., & Crane, K. (2020) · ACM Transactions on Graphics · doi:10.1145/3414685.3417839 · Cited by 99
Digital elevation models and TIN algorithms
van Kreveld, M. J. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63818-0_3 · Cited by 97
A survey of geodesic paths on 3D surfaces
Bose, P. K., Maheshwari, A., Shu, C., & Wuhrer, S. (2011) · Computational Geometry · doi:10.1016/j.comgeo.2011.05.006 · Cited by 92
Cline, D., Jeschke, S., White, K. B., Razdan, A., & Wonka, P. (2009) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2009.01499.x · Cited by 91
Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem
Ying, X., Wang, X., & He, Y. (2013) · ACM Transactions on Graphics · doi:10.1145/2508363.2508379 · Cited by 88
Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation
Qin, Y., Han, X., Yu, H., Yu, Y., & Zhang, J. (2016) · ACM Transactions on Graphics · doi:10.1145/2897824.2925930 · Cited by 82
Rowe, N. C., & Ross, R. S. (1990) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.62043 · Cited by 82
Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes
Wang, X., Ying, X., Liu, Y., Xin, S., Wang, W., Gu, X. D., Müeller-Wittig, W., & He, Y. (2014) · Computer-Aided Design · doi:10.1016/j.cad.2014.08.023 · Cited by 80
Shortest paths among obstacles in the plane
Mitchell, J. S. B. (1993) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/160985.161156 · Cited by 80
Self-citationUnunfoldable polyhedra with convex faces
Bern, M. W., Demaine, E. D., Eppstein, D., Kuo, E., Mantler, A., & Snoeyink, J. S. (2002) · Computational Geometry · doi:10.1016/s0925-7721(02)00091-3 · Cited by 80
Body Topography Parcellates Human Sensory and Motor Cortex
Kuehn, E., Dinse, J., Jakobsen, E., Long, X., Schäfer, A., Bazin, P., Villringer, A., Sereno, M. I., & Margulies, D. S. (2017) · Cerebral Cortex · doi:10.1093/cercor/bhx026 · Cited by 79
Approximating shortest paths on a convex polytope in three dimensions
Agarwal, P. K., Har-Peled, S., Sharir, M., & Varadarajan, K. (1997) · Journal of the ACM · doi:10.1145/263867.263869 · Cited by 79
Approximating Shortest Paths on Weighted Polyhedral Surfaces
Lanthier, M. A., Maheshwari, A., & Sack, J.-R. (2001) · Algorithmica · doi:10.1007/s00453-001-0027-5 · Cited by 77
New results on shortest paths in three dimensions
Mitchell, J. S. B., & Sharir, M. (2004) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/997817.997839 · Cited by 77
Self-citationPlanar graphs, negative weight edges, shortest paths, and near linear time
Fakcharoenphol, J., & Rao, S. B. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959897 · Cited by 77
Optimally cutting a surface into a disk
Erickson, J., & Har-Peled, S. (2002) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/513400.513430 · Cited by 77
Tsagkrasoulis, D., Hysi, P. G., Spector, T. D., & Montana, G. (2017) · Scientific Reports · doi:10.1038/srep45885 · Cited by 75
Autonomous Exploration and Motion Planning for an Unmanned Aerial Vehicle Navigating Rivers
Nuske, S. T., Choudhury, S., Jain, S., Chambers, A., Yoder, L., Scherer, S., Chamberlain, L., Cover, H., & Singh, S. (2015) · Journal of Field Robotics · doi:10.1002/rob.21596 · Cited by 74
Diourté, A., Bugarin, F., Bordreuil, C., & Segonds, S. (2020) · Additive manufacturing · doi:10.1016/j.addma.2020.101622 · Cited by 74
Efficient piecewise-linear function approximation using the uniform metric
Goodrich, M. T. (1995) · Discrete & Computational Geometry · doi:10.1007/bf02570717 · Cited by 74
Geometric triangulations and discrete Laplacians on manifoldsPreprint
Glickenstein, D. A. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0508188 · Cited by 74
A new algorithm for shortest paths among obstacles in the plane
Mitchell, J. S. B. (1991) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/bf01530888 · Cited by 73
Self-citationApproximate shortest path on a polyhedral surface and its applications
Kanai, T., & Suzuki, H. (2001) · Computer-Aided Design · doi:10.1016/s0010-4485(01)00097-5 · Cited by 70
Energy-Efficient Coverage Path Planning for General Terrain Surfaces
Wu, C., Dai, C., Gong, X., Liu, Y., Wang, J., Gu, X. D., & Wang, C. C. L. (2019) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2019.2899920 · Cited by 69
Estimating shortest paths and minimal distances on digitized three-dimensional surfaces
Kiryati, N., & Székely, G. J. (1993) · Pattern Recognition · doi:10.1016/0031-3203(93)90018-r · Cited by 69
Geodesic Fréchet distance inside a simple polygon
Cook, A. F., & Wenk, C. (2010) · ACM Transactions on Algorithms · doi:10.1145/1868237.1868247 · Cited by 68
Folding and Unfolding in Computational Geometry
O’Rourke, J. (2000) · Lecture notes in computer science · doi:10.1007/978-3-540-46515-7_22 · Cited by 68
Zrenner, M., Gradl, S., Jensen, U. J., Ullrich, M., & Eskofier, B. M. (2018) · Sensors · doi:10.3390/s18124194 · Cited by 67
Splitting (complicated) surfaces is hard
Chambers, E. W., de Verdière, É. C., Erickson, J., Lazarus, F., & Whittlesey, K. (2008) · Computational Geometry · doi:10.1016/j.comgeo.2007.10.010 · Cited by 67
Optimal robust path planning in general environments
Hu, T. C., Kahng, A. B., & Robins, G. (1993) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.265921 · Cited by 67
Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes
Xu, C., Wang, T. Y., Liu, Y., Liu, L., & He, Y. (2015) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2015.2407404 · Cited by 64
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.