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
Items 201–300 of 807
Walking On Broken Mesh: Defect‐Tolerant Geodesic Distances and Parameterizations
Campen, M., & Kobbelt, L. P. (2011) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2011.01896.x · Cited by 31
Adaptive spacetime meshing for discontinuous Galerkin methods
Thite, S. (2008) · Computational Geometry · doi:10.1016/j.comgeo.2008.07.003 · Cited by 31
Geodesic Bezier Curves: a Tool for Modeling on Triangulations
Martínez, D., Carvalho, P. C. P., & Velho, L. C. P. R. (2007) · Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI) · doi:10.1109/sibgrapi.2007.38 · Cited by 31
An Improved Approximation Algorithm for Computing Geometric Shortest Paths
Aleksandrov, L., Maheshwari, A., & Sack, J.-R. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45077-1_23 · Cited by 30
Pattern-Based Cloth Registration and Sparse-View Animation
Halimi, O., Stuyck, T., Xiang, D., Bagautdinov, T., Wen, H., Kimmel, R., Shiratori, T., Wu, C., Sheikh, Y. A., & Prada, F. (2022) · ACM Transactions on Graphics · doi:10.1145/3550454.3555448 · Cited by 29
Constant-time O (1) all pairs geodesic distance query on triangle meshes
Xin, S., Ying, X., & He, Y. (2011) · ACM SIGGRAPH Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia (SIGGRAPH Asia) · doi:10.1145/2077378.2077407 · Cited by 29
Simplicial Dijkstra and A∗Algorithms: From Graphs to Continuous Spaces
Yershov, D. S., & LaValle, S. M. (2012) · Advanced Robotics · doi:10.1080/01691864.2012.729559 · Cited by 29
Azernikov, S. (2008) · ACM Symposium on Solid and Physical Modeling (SPM) · doi:10.1145/1364901.1364936 · Cited by 29
A Pseudopolynomial Algorithm for Alexandrov’s Theorem
Kane, D. M., Price, G. N., & Demaine, E. D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03367-4_38 · Cited by 29
Delaunay mesh simplification with differential evolution
Yi, R., Liu, Y., & He, Y. (2018) · ACM Transactions on Graphics · doi:10.1145/3272127.3275068 · Cited by 29
Wrapping spheres with flat paper
Demaine, E. D., Demaine, M. L., Iacono, J., & Langerman, S. (2009) · Computational Geometry · doi:10.1016/j.comgeo.2008.10.006 · Cited by 29
Efficiently computing geodesic offsets on triangle meshes by the extended Xin–Wang algorithm
Xin, S., Ying, X., & He, Y. (2011) · Computer-Aided Design · doi:10.1016/j.cad.2011.08.027 · Cited by 29
Approximation Algorithms for Minimum-Width Annuli and Shells
Agarwal, P. K., Aronov, B. S., Har-Peled, S., & Shark, M. (2000) · Discrete & Computational Geometry · doi:10.1007/s4540010062 · Cited by 29
The Number of Shortest Paths on the Surface of a Polyhedron
Mount, D. M. (1990) · SIAM Journal on Computing · doi:10.1137/0219040 · Cited by 29
Self-citationParallel rectilinear shortest paths with rectangular obstacles
Atallah, M. J., & Chen, D. Z. (1991) · Computational Geometry · doi:10.1016/0925-7721(91)90002-v · Cited by 29
Comparing Direct Measurements and Three-Dimensional (3D) Scans for Evaluating Facial Soft Tissue
Gašparović, B., Morelato, L., Lenac, K., Mauša, G., Zhurov, A. I., & Katić, V. (2023) · Sensors · doi:10.3390/s23052412 · Cited by 28
Texture brush: an interactive surface texturing interface
Sun, Q., Zhang, L., Zhang, M., Ying, X., Xin, S., Xia, J., & He, Y. (2013) · ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D) · doi:10.1145/2448196.2448221 · Cited by 27
Geodesic paths on triangular meshes
Martínez, D., Velho, L. C. P. R., & Carvalho, P. C. (2004) · Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI) · doi:10.1109/sibgra.2004.1352963 · Cited by 27
SHORTEST PATH QUERIES IN RECTILINEAR WORLDS
de Berg, M., van Kreveld, M. J., Nilsson, B. J., & Overmars, M. H. (1992) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195992000172 · Cited by 27
Semi-Continuity of Skeletons in Two-Manifold and Discrete Voronoi Approximation
Liu, Y. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2430342 · Cited by 26
A near-optimal algorithm for shortest paths among curved obstacles in the plane
Hershberger, J. E., Suri, S., & Yıldız, H. (2013) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/2462356.2462374 · Cited by 26
An optimization-driven approach for computing geodesic paths on triangle meshes
Liu, B., Chen, S., Xin, S., He, Y., Liu, Z., & Zhao, J. (2017) · Computer-Aided Design · doi:10.1016/j.cad.2017.05.022 · Cited by 26
HumanGPS: Geodesic PreServing Feature for Dense Human Correspondences
Tan, F., Tang, D., Dou, M., Guo, K., Pandey, R., Keskin, C., Du, R., Sun, D., Bouaziz, S., Fanello, S., et al. (2021) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr46437.2021.00186 · Cited by 26
Thaw: A Tool for Approximating Cut Loci on a Triangulation of a Surface
Itoh, J., & Sinclair, R. M. (2004) · Experimental Mathematics · doi:10.1080/10586458.2004.10504543 · Cited by 26
Cortical surface‐based threshold‐free cluster enhancement and cortexwise mediation
Lett, T. A. P., Waller, L., Tost, H., Veer, I. M., Nazeri, A., Erk, S., Brandl, E. J., Charlet, K., Beck, A., Vollstädt‐Klein, S., et al. (2017) · Human Brain Mapping · doi:10.1002/hbm.23563 · Cited by 26
Finding shortest path on land surface
Lian, L., & Wong, R. C.-W. (2011) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1989323.1989369 · Cited by 26
Sublinear geometric algorithms
Chazelle, B., Liu, D., & Magen, A. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780620 · Cited by 26
Approximating shortest paths on a nonconvex polyhedron
Varadarajan, K., & Agarwal, P. K. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646107 · Cited by 26
Fast Construction of Discrete Geodesic Graphs
Adikusuma, Y. Y., Fang, Z., & He, Y. (2020) · ACM Transactions on Graphics · doi:10.1145/3144567 · Cited by 25
Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions
Har-Peled, S. (1997) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/262839.263003 · Cited by 25
Physical distance to sensory-motor landmarks predicts language function
Wang, X., Krieger‐Redwood, K., Zhang, M., Cui, Z., Wang, X., Karapanagiotidis, T., Du, Y., Leech, R., Bernhardt, B. C., Margulies, D. S., et al. (2022) · Cerebral Cortex · doi:10.1093/cercor/bhac344 · Cited by 24
Geometry-Aware Coverage Path Planning for Depowdering on Complex 3D Surfaces
Do, V., & Pham, Q. (2023) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2023.3296943 · Cited by 24
Wang, X., Krieger‐Redwood, K., Lyu, B., Lowndes, R., Wu, G., Souter, N. E., Wang, X., Kong, R., Shafiei, G., Bernhardt, B. C., et al. (2024) · Journal of Neuroscience · doi:10.1523/jneurosci.2223-23.2024 · Cited by 24
Designing approximation minimal parametric surfaces with geodesics
Li, C., Wang, R.-H., & Zhu, C.-G. (2013) · Applied Mathematical Modelling · doi:10.1016/j.apm.2013.01.035 · Cited by 24
Wu, Z., Zhao, F., Xia, J., Wang, L., Lin, W., Gilmore, J. H., Li, G., & Shen, D. G. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-32248-9_55 · Cited by 24
Aichholzer, O., Aurenhammer, F., Chen, D. Z., Lee, D. T., & Papadopoulou, E. (1999) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195999000169 · Cited by 24
Practical methods for approximating shortest paths on a convex polytope in R3
Hershberger, J. E., & Suri, S. (1995) · Symposium on Discrete Algorithms · doi:10.5555/313651.313787 · Cited by 24
Computational geometry column 18
O’Rourke, J. (1993) · ACM SIGACT News · doi:10.1145/152992.152994 · Cited by 24
Parameterization of Manifold Triangulations
Floater, M. S., Hormann, K., Reimers, M., Chui, C. K., & Schumaker, L. L. (2002) · Cited by 24
Optimal piecewise linear motion of an object among obstacles
Papadimitriou, C. H., & Silverberg, E. B. (1987) · Algorithmica · doi:10.1007/bf01840372 · Cited by 24
Self-citationMolecular architecture of thylakoid membranes within intact spinach chloroplasts
Wietrzyñski, W., Lamm, L., Wood, W. H. J., Loukeri, M.-J., Malone, L. A., Peng, T., Johnson, M. P., & Engel, B. D. (2025) · eLife · doi:10.7554/elife.105496.3 · Cited by 23
Khakpour, H., Birglen, L., & Tahan, A. S. (2014) · The International Journal of Advanced Manufacturing Technology · doi:10.1007/s00170-014-6504-1 · Cited by 23
An efficient algorithm for a visibility-based surveillance-evasion game
Takei, R., Tsai, Y. R., Zhou, Z., & Landa, Y. (2014) · Communications in Mathematical Sciences · doi:10.4310/cms.2014.v12.n7.a7 · Cited by 23
Water-Distance-Based Kriging in Chesapeake Bay
Murphy, R. R., Perlman, E., Ball, W. P., & Curriero, F. C. (2014) · Journal of Hydrologic Engineering · doi:10.1061/(asce)he.1943-5584.0001135 · Cited by 23
Polyline‐sourced Geodesic Voronoi Diagrams on Triangle Meshes
Xu, C., Liu, Y., Sun, Q., Li, J., & He, Y. (2014) · Computer Graphics Forum · doi:10.1111/cgf.12484 · Cited by 23
Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion
Herholz, P., Haase, F., & Alexa, M. (2017) · Computer Graphics Forum · doi:10.1111/cgf.13116 · Cited by 23
CyberTape: an interactive measurement tool on polyhedral surface
Wang, C. C. L. (2004) · Computers & Graphics · doi:10.1016/j.cag.2004.06.011 · Cited by 23
Constructing approximate shortest path maps in three dimensions
Har-Peled, S. (1998) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/276884.276927 · Cited by 23
Shortest Path to Boundary for Self-Intersecting Meshes
Chen, A. H., Diaz, E., & Yuksel, C. (2023) · ACM Transactions on Graphics · doi:10.1145/3592136 · Cited by 22
Discrete Time Evolution Process Descriptor for Shape Analysis and Matching
Melzi, S., Ovsjanikov, M., Roffo, G., Cristani, M., & Castellani, U. (2018) · ACM Transactions on Graphics · doi:10.1145/3144454 · Cited by 22
Monochromatic and bichromatic reverse nearest neighbor queries on land surfaces
Yan, D., Zhao, Z., & Ng, W. (2012) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2396761.2396880 · Cited by 22
Computational geometry column 35
O’Rourke, J. (1999) · ACM SIGACT News · doi:10.1145/568547.568559 · Cited by 22
Moet, E., van Kreveld, M. J., & van der Stappen, A. F. (2008) · Computational Geometry · doi:10.1016/j.comgeo.2007.10.008 · Cited by 22
A cortical surface-based geodesic distance package for Python
Margulies, D. S., Falkiewicz, M., & Huntenburg, J. M. (2016) · GigaScience · doi:10.1186/s13742-016-0147-0-q · Cited by 22
Part decomposition of 3d surfaces
Page, D. L., & Abidi, M. A. (2003) · Cited by 22
Storing the subdivision of a polyhedral surface
Mount, D. M. (1987) · Discrete & Computational Geometry · doi:10.1007/bf02187877 · Cited by 22
Self-citationApproximate shortest path and distance queries in networks
Sommer, C. (2010) · Cited by 22
Daniel, T., Casenave, F., Akkari, N., Ryckelynck, D., & Rey, C. (2022) · Mechanics & Industry · doi:10.1051/meca/2022001 · Cited by 21
Xin, S., Wang, P., Xu, R., Yan, D.-M., Chen, S., Wang, W., Zhang, C., & Tu, C. (2022) · ACM Transactions on Graphics · doi:10.1145/3550454.3555453 · Cited by 21
Learning the Geodesic Embedding with Graph Neural Networks
Pang, B., Zheng, Z., Wang, G., & Wang, P. (2023) · ACM Transactions on Graphics · doi:10.1145/3618317 · Cited by 21
Multimodal gradients of basal forebrain connectivity across the neocortex
Chakraborty, S., Haast, R. A. M., Onuska, K. M., Kanel, P., Prado, M. A. M., Prado, V. F., KHAN, A. R., & Schmitz, T. W. (2024) · Nature Communications · doi:10.1038/s41467-024-53148-x · Cited by 21
Wormhole Loss for Partial Shape Matching
Bracha, A., Dagès, T., & Kimmel, R. (2024) · neural information processing systems · doi:10.52202/079017-4171 · Cited by 21
Fuzzy Geodesics and Consistent Sparse Correspondences For: eformable Shapes
Sun, J. Z., Chen, X., & Funkhouser, T. A. (2010) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2010.01762.x · Cited by 21
Tool-adaptive offset paths on triangular mesh workpiece surfaces
Kout, A., & Müller, H. (2014) · Computer-Aided Design · doi:10.1016/j.cad.2014.01.009 · Cited by 21
Approximate Euclidean shortest paths amid convex obstacles
Agarwal, P. K., Sharathkumar, R., & Yu, H. (2009) · Symposium on Discrete Algorithms · doi:10.5555/1496770.1496802 · Cited by 21
Modeling on triangulations with geodesic curves
Martínez, D., Carvalho, P. C. P., & Velho, L. C. P. R. (2008) · The Visual Computer · doi:10.1007/s00371-008-0298-9 · Cited by 21
Compliant motion planning with geometric models
Bajaj, C., & Kim, M. G. (1987) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/41958.41976 · Cited by 21
Yu, H., Zhang, J., & Jiao, Z. (2014) · Mathematical Problems in Engineering · doi:10.1155/2014/860136 · Cited by 20
Geodesics on the regular tetrahedron and the cube
Davis, D., Dods, V., Traub, C. M., & Yang, J. (2016) · Discrete Mathematics · doi:10.1016/j.disc.2016.07.004 · Cited by 20
Photogrammetric Surveys and Geometric Processes to Analyse and Monitor Red Coral Colonies
Royer, J., Nawaf, M. M., Merad, D., Saccone, M., Bianchimani, O., Garrabou, J., Ledoux, J., López‐Sanz, À., & Drap, P. (2018) · Journal of Marine Science and Engineering · doi:10.3390/jmse6020042 · Cited by 20
Chu, S., & Guilleminot, J. (2019) · Mechanics Research Communications · doi:10.1016/j.mechrescom.2019.01.008 · Cited by 20
Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models
Wang, P., Xin, S., Tu, C., Yan, D.-M., Zhou, Y., & Zhang, C. (2020) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2020.101848 · Cited by 20
Adaptive and robust curve smoothing on surface meshes
Lawonn, K., Gasteiger, R., Rössl, C., & Preim, B. (2014) · Computers & Graphics · doi:10.1016/j.cag.2014.01.004 · Cited by 20
Xin, S., & Wang, G. (2010) · Computer-Aided Design · doi:10.1016/j.cad.2010.05.009 · Cited by 20
Approximate Euclidean Shortest Paths amid Convex Obstacles
Agarwal, P. K., Sharathkumar, R., & Yu, H. (2009) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973068.32 · Cited by 20
On maximum flows in polyhedral domains
Mitchell, J. S. B. (1988) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/73393.73428 · Cited by 20
Self-citationMinimizing turns for discrete movement in the interior of a polygon
Reif, J. H., & Storer, J. A. (1987) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1987.1087092 · Cited by 20
Moet, E., van Kreveld, M. J., & van der Stappen, A. F. (2006) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1137856.1137885 · Cited by 20
A unified framework for isotropic meshing based on narrow-band Euclidean distance transformation
Leung, Y., Wang, X., He, Y., Liu, Y., & Wang, C. C. L. (2015) · Computational Visual Media · doi:10.1007/s41095-015-0022-4 · Cited by 19
Classifying fragments of terracotta warriors using template-based partial matching
Du, G., Zhou, M., Yin, C., Wu, Z., & Shui, W. (2017) · Multimedia Tools and Applications · doi:10.1007/s11042-017-5396-0 · Cited by 19
Hartmann, R., Weiherer, M., Schiltz, D., Seitz, S., Lotter, L., Anker, A., Palm, C., Prantl, L., & Brébant, V. (2020) · Aesthetic Plastic Surgery · doi:10.1007/s00266-020-01749-4 · Cited by 19
Computing approximate shortest paths on convex polytopes
Agarwal, P. K., Har-Peled, S., & Karia, M. (2000) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/336154.336213 · Cited by 19
Splitting (complicated) surfaces is hard
Chambers, E. W., de Verdière, É. C., Erickson, J., Lazarus, F., & Whittlesey, K. (2006) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1137856.1137918 · Cited by 19
Computational topology of graphs on surfacesPreprint
de Verdière, É. C. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.05358 · Cited by 19
Surface-Filling Curve Flows via Implicit Medial Axes
Noma, Y., Sellán, S., Sharp, N., Singh, K. S., & Jacobson, A. (2024) · ACM Transactions on Graphics · doi:10.1145/3658158 · Cited by 18
Mathematical Tools for Shape Analysis and Description
Biasotti, S., Falcidieno, B., Giorgi, D., & Spagnuolo, M. (2014) · Synthesis lectures on computer graphics and animation · doi:10.1007/978-3-031-79558-9 · Cited by 18
Shortest Path Problems on a Polyhedral Surface
Cook, A. F., & Wenk, C. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03367-4_14 · Cited by 18
A real-time network approach for including obstacles and flight dynamics in UAV route planning
Myers, D., Batta, R., & Karwan, M. H. (2016) · The Journal of Defense Modeling and Simulation Applications Methodology Technology · doi:10.1177/1548512916630183 · Cited by 18
Constant cusp toolpath generation in configuration space based on offset curves
Hauth, S., Richterich, C., Glasmacher, L., & Linsen, L. (2010) · The International Journal of Advanced Manufacturing Technology · doi:10.1007/s00170-010-2817-x · Cited by 18
Abnormal Profiles of Local Functional Connectivity Proximal to Focal Cortical Dysplasias
Besseling, R. M. H., Jansen, J. F. A., de Louw, A. J. A., Vlooswijk, M. C. G., Hoeberigs, M. C., Aldenkamp, A. P., Backes, W. H., & Hofman, P. A. M. (2016) · PLoS ONE · doi:10.1371/journal.pone.0166022 · Cited by 18
A minimalistic approach for fast computation of geodesic distances on triangular meshes
Calla, L. A. R., Perez, L. J. F., & Montenegro, A. A. (2019) · Computers & Graphics · doi:10.1016/j.cag.2019.08.014 · Cited by 18
Bähr, M., Buhl, J., Radow, G., Schmidt, J., Bambach, M., Breuß, M., & Fügenschuh, A. R. (2020) · Optimization and Engineering · doi:10.1007/s11081-020-09552-5 · Cited by 18
Hahmann, S., Belyaev, A. G., Busé, L., Elber, G., Mourrain, B., & Rössl, C. (2007) · Mathematics and visualization · doi:10.1007/978-3-540-33265-7_1 · Cited by 18
A global algorithm to compute defect-tolerant geodesic distance
Xin, S., Quynh, D. T. P., Ying, X., & He, Y. (2012) · SIGGRAPH Asia Technical Briefs · doi:10.1145/2407746.2407769 · Cited by 18
An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
Schreiber, Y., & Sharir, M. (2006) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1137856.1137862 · Cited by 18
Approximation algorithms for shortest descending paths in terrains
Ahmed, M., Das, S., Lodha, S., Lubiw, A., Maheshwari, A., & Roy, S. (2009) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2009.05.001 · Cited by 18
Exact and approximate algorithms for the calculation of shortest paths
Li, F., & Klette, R. (2006) · University of Minnesota Digital Conservancy (University of Minnesota) · Cited by 18
Approximating shortest paths on a convex polytope in three dimensions
Har-Peled, S., Sharir, M., & Varadarajan, K. (1996) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/237218.237402 · Cited by 18
Gomes, D. F., Luo, S., & Paoletti, P. (2023) · Robotics: Science and Systems · doi:10.15607/rss.2023.xix.035 · Cited by 17
Macroscale brain states support the control of semantic cognition
Wang, X., Krieger‐Redwood, K., Cui, Y., Smallwood, J., Du, Y., & Jefferies, E. (2024) · Communications Biology · doi:10.1038/s42003-024-06630-7 · Cited by 17
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.