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 601–700 of 807
Medial Residues of Piecewise Linear Manifolds
Chambers, E. W., Ju, T., & Letscher, D. (2013) · Canadian Conference on Computational Geometry · Cited by 2
Simple, Robust, Constant-Time Bounds on Surface Geodesic Distances using Point Landmarks
Burghard, O., & Klein, R. (2015) · Eurographics · doi:10.2312/vmv.20151253 · Cited by 2
Topological analysis of voxelized objects by discrete geodesic Reeb graph
Bhunre, P. K., & Bhowmick, P. (2017) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2017.09.002 · Cited by 2
Path Planning on Quadric Surfaces and Its Application
Sun, C., Jan, G. E., Lu, C., & Yang, K. (2018) · InTech eBooks · doi:10.5772/intechopen.72573 · Cited by 2
Finding Shortest Paths in a Sequence of Triangles in 3D by the Planar Unfolding
An, P. T. (2019) · Numerical Functional Analysis and Optimization · doi:10.1080/01630563.2019.1566927 · Cited by 2
Falque, R., Vidal‐Calleja, T., McPhee, M. J., Toohey, E. S., & Alempijevic, A. (2021) · IEEE International Symposium on Computational Intelligence and Informatics (CINTI) · doi:10.1109/cinti53070.2021.9668608 · Cited by 2
Discrete exterior calculus for meshes with concyclic polygons
Schier, A., & Klein, R. (2023) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2023.102170 · Cited by 2
GBGVD: Growth-based geodesic Voronoi diagrams
Qi, Y., Zong, C., Zhang, Y., Chen, S., Xu, M., Ran, L., Xu, J., Xin, S., & He, Y. (2023) · Graphical Models · doi:10.1016/j.gmod.2023.101196 · Cited by 2
Bishop, J. E. (2024) · Computer Methods in Applied Mechanics and Engineering · doi:10.1016/j.cma.2023.116725 · Cited by 2
Roy, S., Das, S., & Nandy, S. C. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24767-8_5 · Cited by 2
Finding the Shortest Path for Quality Assurance of Electric Components
Kageura, M., & Shimada, K. (2002) · ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference (IDETC/CIE) · doi:10.1115/detc2002/dac-34117 · Cited by 2
Matching and morphing of isometric models
Wuhrer, S. (2009) · Carleton University's Institutional Repository (MacOdrum Library, Carleton University) · doi:10.22215/etd/2009-06338 · Cited by 2
SHORTEST PATHS WITH SINGLE-POINT VISIBILITY CONSTRAINT
Khosravi, R., & Ghodsi, M. (2006) · Scientia Iranica · Cited by 2
Path planning with spatial and temporal constraints.
Berger, F. (2010) · bonndoc (University of Bonn) · Cited by 2
Harabor, D. (2014) · ANU Open Research (Australian National University) · doi:10.25911/5d611e273981b · Cited by 2
Interactive three-dimensional image analysis and visualization using graphics hardware
Jeong, W. (2008) · Cited by 2
Polyline Simplification under the Local Fréchet Distance has Almost-Quadratic Runtime in 2DPreprint
Storandt, S., & Zink, J. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2201.01344 · Cited by 2
The existence of inversive distance circle packing on polyhedral surfacePreprint
Zhu, X. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2311.01272 · Cited by 2
Optimal path planning using spatial neighborhood properties
Bhattacharya, P. (2007) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/prism/1209 · Cited by 2
Reconstruction de solides à partir d'acquisitions surfaciques
Synave, R. (2009) · theses.fr (ABES) · doi:10.70675/6e02a015z0cc7z499dz927fz5cef37eac28d · Cited by 2
Petit, M. (2023) · theses.fr (ABES) · doi:10.70675/e7b5bdb5ze98bz449czbd7dzcab72aa23395 · Cited by 2
Globally Adaptive and Locally Regular Point Discretization of Implicit Surface GeometriesPreprint
Schulze, L. J., & Sbalzarini, I. F. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.03803 · Cited by 2
Which Anatomical Directions to Quantify Local Right Ventricular Strain in 3D Echocardiography?
Folco, M. D., Dargent, T., Bernardino, G., Clarysse, P., & Duchateau, N. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-35302-4_62 · Cited by 1
Unsupervised Anthropometric Measurements from 3D Scans Using Automated Template Registration
Inguglia, A., Vitucci, G., & Paraskevopoulos, I. (2024) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2024.09.276 · Cited by 1
An Efficient Algorithm for Approximate Polyline-Sourced Offset Computation on Triangulated Surfaces
Meng, W., Yu, H., Geng, Y., & Bo, P. (2025) · Tsinghua Science & Technology · doi:10.26599/tst.2024.9010239 · Cited by 1
Latissimus-dorsi-inspired trunk torsion mechanism for quadruped robot spine design
Matsumoto, O., Tanaka, H., Tadakuma, K., & Hosoda, K. (2025) · Advanced Robotics · doi:10.1080/01691864.2025.2528829 · Cited by 1
Visualizing black holes and wormholes through raytracing
Mehta, N., & Ripperda, B. (2025) · Journal of Emerging Investigators · doi:10.59720/24-074 · Cited by 1
Efficient Path Oracles for Proximity Queries on Point Clouds
Yan, Y., & Wong, R. C.-W. (2025) · ACM Transactions on Database Systems · doi:10.1145/3770577 · Cited by 1
Registration-Free Monitoring of Unstructured Point Cloud Data via Intrinsic Geometrical Properties
Patalano, M., Capizzi, G., & Paynabar, K. (2026) · Technometrics · doi:10.1080/00401706.2026.2702438 · Cited by 1
Learning Sparse Singularities for Cross Field Design
Zhang, X., Bao, H., & Huang, J. (2026) · ACM Transactions on Graphics · doi:10.1145/3787520 · Cited by 1
Automatic accurate craniofacial reconstruction based on geodesic statistical model
Liu, W., Zhao, J., & Lin, W. A. N. G. (2026) · Virtual Reality & Intelligent Hardware · doi:10.1016/j.vrih.2026.03.003 · Cited by 1
Plane-Constrained Geodesic Curves on Point Clouds
Azariadis, P. N., & Agathos, A. (2026) · Algorithms · doi:10.3390/a19080684 · Cited by 1
Discrete Geodesics and Cellular Automata
Arrighi, P. J., & Dowek, G. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-26841-5_11 · Cited by 1
Minimal Distortion 3-D Watermarking Using Statistics Of Geodesic Distances
Gerasimou, S. (2012) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.42899 · Cited by 1
3D Objects Retrieval using Geodesic Distance Based on Eikonal equation
Naji, D., Fakir, M., & Bencharef, O. (2015) · Indonesian Journal of Electrical Engineering and Computer Science · doi:10.11591/ijeecs.v15.i3.pp597-604 · Cited by 1
Fast numerical algorithms for optimal robot motion planning
Yershov, D. S. (2013) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 1
Mapping and Pocketing Techniques for Laser Marking of 2D Shapes on 3D Curved Surfaces
Devigili, F., Lotto, D., & Amicis, R. D. (2016) · Smart innovation, systems and technologies · doi:10.1007/978-3-319-39345-2_39 · Cited by 1
Zwawi, M. A. M. (2015) · STARS (University of Central Florida) · Cited by 1
3D Objects Retrieval using Geodesic Distance Based on Eikonal equation
Naji, D., Fakir, M., & Bencharef, O. (2015) · TELKOMNIKA Indonesian Journal of Electrical Engineering · doi:10.11591/tijee.v15i3.1579 · Cited by 1
Voronoi-Based Extraction of a Feature Skeleton from Noisy Triangulated Surfaces
Wekel, T., & Hellwich, O. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37444-9_9 · Cited by 1
Li, M. J., & Geng, W. D. (2013) · Applied Mechanics and Materials · doi:10.4028/www.scientific.net/amm.333-335.95 · Cited by 1
Vehicle Path Verification Using Wireless Sensor Networks
Howser, G., Chellappan, S., & Paruchuri, V. (2013) · International Conference on Advanced Information Networking and Applications Workshops (WAINA) · doi:10.1109/waina.2013.220 · Cited by 1
Fast Neighborhood Search on Polygonal Meshes
Rocca, L., Giorgis, N. D., Panozzo, D., & Puppo, E. (2011) · CINECA IRIS Institutial Research Information System (University of Genoa) · doi:10.2312/localchapterevents/italchap/italianchapconf2011/015-021 · Cited by 1
A simple and local method for computing quasi-conformal map on 3D surfaces
Zhang, M., & He, Y. (2013) · Computer-Aided Design · doi:10.1016/j.cad.2013.08.031 · Cited by 1
Approximate Geodesics on Smooth Surfaces of Arbitrary Topology
Lai, S., & Cheng, F. F. (2011) · Computer-Aided Design and Applications · doi:10.3722/cadaps.2011.499-506 · Cited by 1
Recognition of 3D Objects Using Heat Diffusion Equations and Random Forests
Naji, D., Fakir, M., Bouikhalene, B., & Elayachi, R. (2016) · International Conference on Computer Graphics, Imaging and Visualization (CGIV) · doi:10.1109/cgiv.2016.39 · Cited by 1
The Shortest Path Finding between two points on a Polyhedral Surface
Petrovna, P. T., Popov, E. V., & Igorevich, R. S. (2014) · Digital Library (University of West Bohemia) · Cited by 1
Navigating Weighted Regions with Scattered Skinny Tetrahedra
Cheng, S.-W., Chiu, M.-K., Jin, J., & Vigneron, A. (2017) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195917600020 · Cited by 1
Shortest Path Problems on a Polyhedral Surface
Wenk, C., & Cook, A. F. (2009) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/dagsemproc.09111.5 · Cited by 1
Pattern Design of Freeform Features on Triangular Meshes
Liu, B. (2019) · Journal of Mechanical Engineering · doi:10.3901/jme.2019.03.120 · Cited by 1
Wave propagation time optimization for geodesic distances calculation using the Heat Method
Wróblewski, A., & Andrzejczak, J. (2019) · Open Physics · doi:10.1515/phys-2019-0027 · Cited by 1
Field-Aware Parameterization for 3D Painting
Xu, S., Li, H., & Keyser, J. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-22514-8_11 · Cited by 1
Ehm, V., Cremers, D., & Bernard, F. (2021) · International Conference on 3D Vision (3DV) · doi:10.1109/3dv53792.2021.00126 · Cited by 1
Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings
Miller, E., & Pak, I. (2006) · Discrete & Computational Geometry · doi:10.1007/s00454-006-1249-0 · Cited by 1
Folco, M. D., Bernardino, G., Clarysse, P., & Duchateau, N. (2026) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2026.3698240 · Cited by 1
Approximate 2D-3D Shape Matching for Interactive Applications
Petzsch, C., Roetzer, P., Lähner, Z., & Bernard, F. (2025) · International Conference on 3D Vision (3DV) · doi:10.1109/3dv66043.2025.00044 · Cited by 1
Ophelders, T., Löffler, M., Silveira, R. I., & Staals, F. (2025) · Journal of computational geometry · doi:10.20382/jocg.v15i2a6 · Cited by 1
Shortest Monotone Descent Path Problem in Polyhedral Terrain
Roy, S., Das, S., & Nandy, S. C. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31856-9_23 · Cited by 1
Hernando, D. (2008) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · Cited by 1
Field D* Pathfinding in Weighted Simplicial Complexes
Perkins, S. J. (2013) · Open University of Cape Town (University of Cape Town) · Cited by 1
Design and Optimization of a Robot for Abrasive Waterjet Polishing of Hydraulic Turbine Blades
Khakpour, H. (2014) · PolyPublie (École Polytechnique de Montréal) · Cited by 1
Intrinsic computation of voronoi diagrams on surfaces and its application
Wang, X. (2015) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/65864 · Cited by 1
Klein, K. (2014) · eScholarship (California Digital Library) · Cited by 1
A Pseudopolynomial Algorithm for Alexandrov's Theorem
Kane, D. M., Price, G. N., & Demaine, E. D. (2008) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/dagsemproc.09111.2 · Cited by 1
Geodesics using Waves: Computing Distances using Wave PropagationPreprint
Sinha, A., & Kazhdan, M. M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1612.02509 · Cited by 1
Efficient and practical algorithms for discrete geodesics
Xiang, Y. (2012) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/54871 · Cited by 1
Locus Techniques for Shortest Path Problems in Robotics
Franklin, W. R., & Akman, V. (1985) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)59974-7 · Cited by 1
Parallel computation of discrete geodesics and its applications
Le, T. H. (2017) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/72861 · Cited by 1
Computational Geometry Column 35Preprint
O’Rourke, J. (1999) · arXiv (Cornell University) · Cited by 1
Uncertainty quantification for industrial design using dictionaries of reduced order modelsPreprint
Daniel, T., Casenave, F., Akkari, N., Ryckelynck, D., & Rey, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.04012 · Cited by 1
Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldingsPreprint
Miller, E., & Pak, I. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0312253 · Cited by 1
Shortest Path Queries on Triangular Irregular Networks and Point Clouds
Yan, Y. (2025) · doi:10.14711/thesis-hdl152313 · Cited by 1
Bounded approximations of geodesics for triangular manifolds with partially missing data
Wuhrer, S., Shu, C., Bose, P., & Azouz, Z. B. (2007) · NPARC · doi:10.4224/8913812 · Cited by 1
Algorithms for Drawing Graphs and Polylines with Straight-Line Segments
Zink, J. (2024) · Online Publication Service of Würzburg University (Würzburg University) · doi:10.25972/opus-35475 · Cited by 1
Clustering basado en redes bayesianas con predictoras continuas: aplicaciones en neurociencia
Luengo-Sánchez, S. (2014) · Hispana · Cited by 1
崇, 金., 宏正, 鈴., 純, 三., & 文彦, 木. (n.d.) · Terrestrial Environment Research Center (University of Tsukuba) · Cited by 1
Bletterer, A. (2018) · theses.fr (ABES) · doi:10.70675/ba8460fbz4786z4549z9c63z7626bf2558f4 · Cited by 1
From Extrinsic to Intrinsic: Geodesic-Guided Representation Learning for 3D Geometric DataPreprint
Zhao, Y., Hou, J., Zhang, Q., Qin, J., & He, Y. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.02268 · Cited by 1
The Quick Dog Jumps the LogPreprint
Blank, L., Driemel, A., Har-Peled, S., & Richter, M. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.09917 · Cited by 1
Global Colon Geometric Structure Analysis Based on Geodesics and Conformal Flattening
Peng, H., Shi, R., Xin, S., & Gu, X. D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-41083-3_13
Parallel Techniques for Paths, Visibility, and Related Problems (Thesis)
Chen, Z. D. (1992) · Purdue e-Pubs (Purdue University System)
Li, F., & Klette, R. (2011) · Springer eBooks · doi:10.1007/978-1-4471-2256-2_7
Practical Conditions for Well-behaved-ness of Anisotropic Voronoi DiagramsPreprint
Cañas, G. D. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.0867
Minimum spanning trees on polyhedra.
Spriggs, M. J., & Keil, J. (1999) · Canadian Conference on Computational Geometry
Gueorguieva, S., Synave, R., & Couture-Veschambre, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17274-8_41
Facility Location on Terrains (Extended Abstract)
Aronov, B. S., van Kreveld, M. J., van Oostrum, R., & Varadarajan, K. (1998)
Geodesic Mesh Processing with Edge-Front based Data Structures
Annuth, H., & Bohn, C.-A. (2014) · International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP) · doi:10.5220/0004718900640075
Algorithms for Optimizing Search Schedules in a Polygon
Bahun, S. (2008) · UWSpace (University of Waterloo)
Computing interesting topological features
Erickson, J., & Chambers, E. W. (2008)
Reconstructing Geometric Structures from Combinatorial and Metric Information
Alam, A. (2015) · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · doi:10.7275/6461420.0
Uniform Sampling in Geodesic Metric for LOD Generation
Hou, W. W., Ding, M., & Lai, X. (2012) · Journal of Software · doi:10.4304/jsw.7.5.1066-1073
Creating high quality indicative routes in heterogeneous virtual environments
Tibboel, M. (2013) · Utrecht University Repository (Utrecht University)
Fast approximation of geodesic based on heuristic estimate
Yaqi, M., & Li, Z. (2010) · International Conference on Computer Design and Applications (ICCDA) · doi:10.1109/iccda.2010.5540779
Fast Computing for the Approximate Straightest Path on Triangular Mesh Surfaces
Jin, Y. H., Li, Z., Shi, J., Zhou, Z., Pan, R., & Jin, X. (2010) · Journal of Computer-Aided Design & Computer Graphics · doi:10.3724/sp.j.1089.2010.10671
Geometric Approximation Algorithms - A Summary Based Approach
Sharathkumar, R. (2012) · DukeSpace (Duke University)
Novel interfaces for modeling and painting
Sun, Q. (2014) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/59547
Geodesics Computation Based on Direction Tracking
Yuan, T., Liao, W., Dai, N., Cheng, X., & Cui, H. (2008) · International Conference on Cyberworlds (CW) · doi:10.1109/cw.2008.93
Fakcharoenphol, J. (2003)
Visualizing and Understanding Patterns of Brain Architecture
Rojer, A. S., & Schwartz, E. (1993) · Springer eBooks · doi:10.1007/978-3-642-58069-7_4
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.