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 501–600 of 807
Isometric 3D Shape Partial Matching Using GD-DNA
Du, G., Yin, C., Zhou, M., Wu, Z., Fan, Y., Duan, F., & Zhou, P. (2018) · Journal of Computer Science and Technology · doi:10.1007/s11390-018-1880-x · Cited by 5
A Survey on 3D Face Recognition based on Geodesics.
Zhao, J., Pan, Z., Duan, F., Lv, Z., Li, J., Zhou, Q., Shang, X., Sun, J., & Pingping, W. (2019) · J. Inf. Hiding Multim. Signal Process. · Cited by 5
Craniofacial Reconstruction Based on Geodesic Regression Model
Chen, Z., Zhao, J., Yu, H., Pan, Z., Jia, B., & Li, J. (2021) · Journal of Computer-Aided Design & Computer Graphics · doi:10.3724/sp.j.1089.2021.18320 · Cited by 5
Subdivision Curves on Surfaces and Applications
Martínez, D., Velho, L. C. P. R., & Carvalho, P. C. P. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85920-8_50 · Cited by 5
Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings
Miller, E., & Pak, I. (2008) · Springer eBooks · doi:10.1007/978-0-387-87363-3_19 · Cited by 5
Detection of constrictions on closed polyhedral surfaces
Hétroy, F., & Attali, D. (2003) · HAL · doi:10.5555/769922.769929 · Cited by 5
The transportation metric and related problems
Ostrovsky-Berman, Y. (2005) · Information Processing Letters · doi:10.1016/j.ipl.2005.05.005 · Cited by 5
Fast geodesic distance approximation using mesh decimation and front propagation
Giard, J., & Macq, B. M. M. (2009) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.805599 · Cited by 5
Geodesic Spanners on Polyhedral Surfaces
Kapoor, S., & Li, X.-Y. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10631-6_23 · Cited by 5
Adikusuma, Y. Y., Huang, Q., & He, Y. (2026) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v40i4.37213 · Cited by 4
Dual-Robot Nonplanar 3D Printing Path Planning and Compensation
Shao, Z., & Cui, Q. (2024) · 3D Printing and Additive Manufacturing · doi:10.1089/3dp.2023.0323 · Cited by 4
Path Planning in an Anisotropic Medium
Dolinskaya, I., & Smith, R. L. (2012) · Cited by 4
ROI Scissor: Interactive Segmentation of Feature Region of Interest in a Triangular Mesh
Moon, J., Ha, Y., Park, S., Kim, M., & Yoon, S. (2023) · Computer Graphics Forum · doi:10.1111/cgf.14803 · Cited by 4
Geodesic distance approximation using a surface finite element method for the p-Laplacian
Potgieter, H., Fetecau, R. C., & Ruuth, S. J. (2025) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2025.102458 · Cited by 4
On the number of shortest descending paths on the surface of a convex terrain
Ahmed, M., Maheshwari, A., Nandy, S. C., & Roy, S. (2010) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2010.12.002 · Cited by 4
A Physicist’s View on Partial 3D Shape Matching
Koehl, P., & Orland, H. (2023) · Algorithms · doi:10.3390/a16070346 · Cited by 4
Non‐Euclidean Sliced Optimal Transport Sampling
Genest, B., Courty, N., & Cœurjolly, D. (2024) · Computer Graphics Forum · doi:10.1111/cgf.15020 · Cited by 4
Compression and Querying of Arbitrary Geodesic Distances
Aiello, R., Banterle, F., Pietroni, N., Malomo, L., Cignoni, P., & Scopigno, R. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-23231-7_26 · Cited by 4
CWave: Theory and Practice of a Fast Single-source Any-angle Path Planning Algorithm
Sinyukov, D. A., & Padır, T. (2019) · Robotica · doi:10.1017/s0263574719000560 · Cited by 4
Three-Dimensional Shortest Path Planning in the Presence of Polyhedral Obstacles
Jiang, K., Seneviratne, L. D., & Earles, S. W. E. (1996) · Proceedings of the Institution of Mechanical Engineers Part C Journal of Mechanical Engineering Science · doi:10.1243/pime_proc_1996_210_209_02 · Cited by 4
Computing generalized higher-order Voronoi diagrams on triangulated surfaces
Fort, M., & Sellarès, J. A. (2009) · Applied Mathematics and Computation · doi:10.1016/j.amc.2009.04.075 · Cited by 4
Reuse of B-spline-based shape interrogation tools for triangular mesh models
Kobashi, Y., Suzuki, J., Joo, H. K., & Maekawa, T. (2012) · 3D Research · doi:10.1007/3dres.02(2012)4 · Cited by 4
Automatic Reconstruction and Web Visualization of Complex PDE Shapes
Pang, M., Sheng, Y., Sourin, A., Castro, G., & Ugail, H. (2010) · International Conference on Cyberworlds (CW) · doi:10.1109/cw.2010.13 · Cited by 4
Near optimal algorithm for the shortest descending path on the surface of a convex terrain
Roy, S. (2012) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2012.03.001 · Cited by 4
Euclidean Shortest Paths on Polyhedra in Three Dimensions
Sackler, B. (2007) · Cited by 4
Efficient runner networks for investment castings
Givler, R. C., & Saylors, D. B. (2000) · International Journal for Numerical Methods in Engineering · doi:10.1002/1097-0207(20000820)48:11<1601::aid-nme894>3.0.co;2-0 · Cited by 4
Werghi, N. (2005) · Pattern Recognition Letters · doi:10.1016/j.patrec.2005.10.002 · Cited by 4
3D shortest path planning in the presence of polyhedral obstacles
Jiang, K., Seneviratne, L. D., & Earles, S. W. E. (2002) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.1993.390850 · Cited by 4
Storing shortest paths for a polyhedron
Chen, J., & Han, Y. (1991) · Lecture notes in computer science · doi:10.1007/3-540-54029-6_166 · Cited by 4
Faster Approximations of Shortest Geodesic Paths on Polyhedra Through Adaptive Priority Queue
Schwartz, W. R., de Rezende, P. J., & Pedrini, H. (2015) · International Conference on Computer Vision Theory and Applications · doi:10.5220/0005260903710378 · Cited by 4
Approximate Point-to-Face Shortest Paths in R^3Preprint
Cheung, Y. K., & Daescu, O. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1004.1588 · Cited by 4
Shortest paths on uncertain terrains
Gray, C. (2009) · cIRcle (University of British Columbia) · doi:10.14288/1.0051736 · Cited by 4
Time-minimal paths amidst moving obstacles in three dimensions
Fujimura, K. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00408-4 · Cited by 4
Computational Surface Flattening: A Voxel-Based Approach
Grossmann, R., Kiryati, N., & Kimmel, R. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45129-3_17 · Cited by 4
Fast Collision-Free Path Planning for Translating Mobiler in Three-Dimensional Space.
Shibata, M., Murakami, T., & Ohnishi, K. (1995) · Journal of the Japan Society for Precision Engineering · doi:10.2493/jjspe.61.1545 · Cited by 4
Curve and surface framing for scientific visualization and domain dependent navigation
Ma, H. (1996) · IUScholarWorks (Indiana University) · Cited by 4
Maintenance de la visibilité d'un point mobile, et applications
Hornus, S., & PUECH, C. (2006) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 4
Fritz, F. J., Streubel, T., Mordhorst, L., Lüthi, N., Edwards, L., Mushumba, H., Püschel, K., Weiskopf, N., Kirilina, E. P., & Mohammadi, S. (2026) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.64898/2026.01.31.702882 · Cited by 4
Parallelised Differentiable Straightest Geodesics for 3D MeshesPreprint
Verninas, H., Korkmaz, C., Zafeiriou, S. P., Birdal, T., & Foti, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2603.15780 · Cited by 4
Machine learning for nonlinear model order reduction
Daniel, T. (2021) · theses.fr (ABES) · doi:10.70675/8271e992z2da6z4466z8651z1f04d1b32782 · Cited by 4
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane
Hershberger, J. E., Suri, S., & Yıldız, H. (2022) · SIAM Journal on Computing · doi:10.1137/21m1428248 · Cited by 3
Manifold Learning: Model Reduction in Engineering
Ryckelynck, D., Casenave, F., & Akkari, N. (2024) · SpringerBriefs in computer science · doi:10.1007/978-3-031-52764-7 · Cited by 3
Pavičić, D. Š. Š., Svirčić, A., Gašparović, B., Šimunović, L., Crnković, S., & Katić, V. (2025) · Applied Sciences · doi:10.3390/app15137529 · Cited by 3
MeshNav3D: Software for Visualizing and Benchmarking Uneven Terrain Planning Algorithms
Jerome, O., Bassey, C., Okeme, C., Малолетов, А. В., & Kulathunga, G. (2025) · Journal of Open Research Software · doi:10.5334/jors.573 · Cited by 3
Löffler, M., Ophelders, T., Silveira, R. I., & Staals, F. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.socg.2023.48 · Cited by 3
Efficient Proximity Queries on Simplified Height Maps
Yan, Y., & Wong, R. C.-W. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3749162 · Cited by 3
Measuring length and girth of a tubular shape by quasi-helixes
Xin, S., Chen, S., Zhao, J., & Pan, Z. (2013) · Computers & Graphics · doi:10.1016/j.cag.2013.10.037 · Cited by 3
A tile-based method for geodesic buffer generation in a virtual globe
Dong, Q., & Chen, J. (2017) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2017.1372764 · Cited by 3
ABLE: Automated Brain Lines Extraction Based on Laplacian Surface Collapse
Fernández‐Pena, A., de Blas, D. M., Navas-Sánchez, F. J., Vidal, L. M., Gordaliza, P. M., Santonja, J., Janssen, J., Carmona, S., Desco, M., & Alemán‐Gómez, Y. (2022) · Neuroinformatics · doi:10.1007/s12021-022-09601-7 · Cited by 3
Compressing Geodesic Information for Fast Point-to-Point Geodesic Distance Queries
Gotsman, C., & Hormann, K. (2022) · SIGGRAPH Asia Conference Papers · doi:10.1145/3550469.3555412 · Cited by 3
Discrete Geodesic Distribution-Based Graph Kernel for 3D Point Clouds
Balcı, M. A., Akgüller, Ö., Batrancea, L. M., & Gãban, L. (2023) · Sensors · doi:10.3390/s23052398 · Cited by 3
Kout, A., & Müller, H. (2013) · The International Journal of Advanced Manufacturing Technology · doi:10.1007/s00170-013-5152-1 · Cited by 3
3D Shape Classification Based on Spectral Function and MDS Mapping
Chen, Z., & Tang, K. (2010) · Journal of Computing and Information Science in Engineering · doi:10.1115/1.3290769 · Cited by 3
Approximate Shortest Descending Paths
Cheng, S.-W., & Jin, J. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973105.11 · Cited by 3
Tracking of object deformations in color and depth video: deformation models and applications
Jordt, A., Reinhold, S., & Koch, R. (2015) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.2190780 · Cited by 3
Approximate ESPs on Surfaces of Polytopes Using a Rubberband Algorithm
Li, F., Klette, R., & Fu, X. (2007) · Springer eBooks · doi:10.1007/978-3-540-77129-6_23 · Cited by 3
Parameterization of 3D Surface Patches by Straightest Distances
Lee, S., & Lee, H. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-72586-2_10 · Cited by 3
Efficient Algorithms for Geometric Shortest Path Query Problems
Chen, D. Z. (1998) · Springer eBooks · doi:10.1007/978-1-4613-0303-9_10 · Cited by 3
Multi-Point Shortest Path in the Complex Road Network Based on Floyd Algorithm
Li, Y., Li, D., & Yu, Y. (2013) · Communications in computer and information science · doi:10.1007/978-3-642-53703-5_38 · Cited by 3
Water Wave Animation on Mesh Surfaces
Liu, S., Jin, X., Wang, C. C. L., & Chen, J. X. (2006) · Computing in Science & Engineering · doi:10.1109/mcse.2006.83 · Cited by 3
Geodesic Fréchet Distance Inside a Simple Polygon
Wenk, C., & Cook, A. F. (2008) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2008.1330 · Cited by 3
An Iterative Algorithm for Computing Shortest Paths Through Line Segments in 3D
Trang, L. H., Truong, Q. C., & Dang, T. K. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70004-5_5 · Cited by 3
Efficient sparse matrix-delayed vector multiplication for discretized neural field model
Fousek, J. (2017) · The Journal of Supercomputing · doi:10.1007/s11227-017-2194-4 · Cited by 3
Computing approximately shortest descending paths on convex terrains via multiple shooting
An, P. T., & Trang, L. H. (2018) · Computational and Applied Mathematics · doi:10.1007/s40314-018-0686-3 · Cited by 3
Constrained Shortest Paths in Terrains and Graphs
Ahmed, M. (2009) · UWSpace (University of Waterloo) · Cited by 3
Computerized Landmarking And Anthropometry Over Laser Scanned 3D Head And Face Surface Meshes
Deo, D. (2006) · Cited by 3
Constraint Shortest Path Computation on Polyhedral Surfaces
Synave, R., Gueorguieva, S., & Desbarats, P. (2008) · Indian Conference on Computer Vision, Graphics and Image Processing · doi:10.1109/icvgip.2008.80 · Cited by 3
Motion planning amidst dynamic obstacles in three dimensions
Fujimura, K. (2002) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.1993.583791 · Cited by 3
Generalized Higher-Order Voronoi Diagrams on Polyhedral Surfaces
Fort, M., & Sellarès, J. A. (2007) · International Symposium on Voronoi Diagrams in Science and Engineering · doi:10.1109/isvd.2007.24 · Cited by 3
Myers, D. J. (2010) · Dissertations & Theses @ SUNY Buffalo,ProQuest Dissertations & Theses Global · Cited by 3
Singh, A. (2016) · UC Berkeley · Cited by 3
Physics-Based Modeling and Simulation of Musculoskeletal Robots
Wittmeier, S. (2014) · mediaTUM (Technical University of Munich) · Cited by 3
Improved Shortest Path Maps with GPU ShadersPreprint
Farias, R., & Kallmann, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.08500 · Cited by 3
DecoSurf: Recursive Geodesic Patterns on Triangle MeshesPreprint
Nazzaro, G., Puppo, E., & Pellacini, F. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.10918 · Cited by 3
Manifold learning via quantum dynamicsPreprint
Kumar, A., & Sarovar, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2112.11161 · Cited by 3
Shining light on data: Geometric data analysis through quantum dynamicsPreprint
Kumar, A., & Sarovar, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2212.00682 · Cited by 3
Physics-informed sensor coverage through structure preserving machine learningPreprint
Shaffer, B. D., Kinch, B., Klobusicky, J. J., Hsieh, M. A., & Trask, N. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2509.10363 · Cited by 3
Shortest Journeys in Directed Temporal Graphs
Cheng, S.-W. (2023) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054123420030 · Cited by 2
Geodesic-based tool path planning for complex free-form surfaces with uncut region elimination
Hong, Z., hu, G., Chen, X., & Xi, J. (2026) · The International Journal of Advanced Manufacturing Technology · doi:10.1007/s00170-025-17358-x · Cited by 2
Wang, D., & Chen, H. (2026) · Probabilistic Engineering Mechanics · doi:10.1016/j.probengmech.2026.103902 · Cited by 2
Diskify: A combinatorial approach to the computation of cut networks on surfaces
Maggioli, F., & Melzi, S. (2026) · Computers & Graphics · doi:10.1016/j.cag.2026.104720 · Cited by 2
Prediction of Protein-Ligand Binding Sites for Cisplatin and Transplatin based on Hydrogen Bonds
dos Anjos, F. A. C., & Barrionuevo, M. V. F. (2015) · Journal of Proteomics & Bioinformatics · doi:10.4172/jpb.1000348 · Cited by 2
DIG: Discrete Iso-contour Geodesics for Topological Analysis of Voxelized Objects
Bhalla, G., & Bhowmick, P. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-39441-1_24 · Cited by 2
Optimal Any-Angle Pathfinding on a Sphere
Rospotniuk, V., & Small, R. (2021) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.12483 · Cited by 2
3D Magic Wand: Interface for Mesh Segmentation Using Harmonic Field
Moon, J., Park, S., & Yoon, S. (2022) · Journal of the Korea Computer Graphics Society · doi:10.15701/kcgs.2022.28.1.11 · Cited by 2
An, P. T., & Phú, H. X. (2022) · Journal of Global Optimization · doi:10.1007/s10898-022-01244-x · Cited by 2
Liang, Y., Ren, X., & Feng, D. (2023) · Journal of Wind Engineering and Industrial Aerodynamics · doi:10.1016/j.jweia.2022.105274 · Cited by 2
The Algorithm of the Path Length Optimization on the Polyhedron Surface
Gumirova, A., Marchevsky, I. K., & Safronov, Y. (2023) · Lecture notes in mechanical engineering · doi:10.1007/978-3-031-37246-9_5 · Cited by 2
Towards geodesic ridge curve for region-wise linear representation of geodesic distance field
Liu, W., Wang, P., Chen, S., Xin, S., Tu, C., He, Y., & Wang, W. (2024) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2024.102291 · Cited by 2
A novel planner framework compatible with various end-effector constraints
Wang, Y., Li, Y., Li, Z., He, H., Chen, S., & Dong, E. (2024) · Robotic Intelligence and Automation · doi:10.1108/ria-02-2024-0043 · Cited by 2
Bishop, J. E., Tupek, M., & Koester, J. J. (2024) · Computer Methods in Applied Mechanics and Engineering · doi:10.1016/j.cma.2024.117459 · Cited by 2
Li, F., Zhu, H., Li, W., Liu, C., Ma, J., & Li, L. (2025) · Geo-spatial Information Science · doi:10.1080/10095020.2024.2446306 · Cited by 2
A new methodology for diagnosis of appendicitis using sonographic images in image mining
Ramu, B., & Thirupathi, D. (2012) · International Conference on Computational Science, Engineering and Information Technology (CCSEIT) · doi:10.1145/2393216.2393336 · Cited by 2
Colaianni, M., Siegl, C., Süßmuth, J., Rott, F., & Greiner, G. (2016) · Eurographics · doi:10.2312/gdf.20161078 · Cited by 2
Space complexity of exact discrete geodesic algorithms on regular triangulations
Liu, Y., Fan, D., Xu, C., & He, Y. (2017) · Information Processing Letters · doi:10.1016/j.ipl.2017.04.005 · Cited by 2
Efficient Algorithms for Geometric Shortest Path Query Problems
Chen, D. Z. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1_47 · Cited by 2
Computing the minimum distance between a point and a curve on mesh
Zhu, F., & Liu, B. (2015) · Journal of Computational Methods in Sciences and Engineering · doi:10.3233/jcm-140514 · Cited by 2
Image-based texture replacement using multiview images
Tal, D., Shimshoni, I., & Tal, A. (2008) · ACM Symposium on Virtual Reality Software and Technology (VRST) · doi:10.1145/1450579.1450619 · Cited by 2
2-Manifold Surface Sampling and Quality Estimation of Reconstructed Meshes
Gong, W., Liu, Y., Tang, K., & Wu, T. (2011) · International Symposium on Voronoi Diagrams in Science and Engineering · doi:10.1109/isvd.2011.11 · Cited by 2
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.