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 401–500 of 807
Shortest path queries in rectilinear worlds of higher dimension (extended abstract)
de Berg, M., van Kreveld, M. J., & Nilsson, B. J. (1991) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/109648.109654 · Cited by 10
Optimistic and pessimistic shortest paths on uncertain terrains
Kholondyrev, Y. (2011) · cIRcle (University of British Columbia) · doi:10.14288/1.0052001 · Cited by 10
COMPUTATIONAL GEOMETRY COLUMN 35
O'ROURKE, J. (1999) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195999000297 · Cited by 9
Human cortical dynamics reflect graded contributions of local geometry and network topography
Royer, J., Paquola, C., Rodríguez‐Cruces, R., Auer, H., Ngo, A., Sahlas, E., Arafat, T., Abdallah, C., Daniel Mansilla, D., Pana, R., et al. (2025) · Nature Communications · doi:10.1038/s41467-025-67740-2 · Cited by 9
Smooth Bijective Projection in a High-order Shell
Liu, S., Ji, Y., Guo, J., Liu, L., & Fu, X. (2024) · ACM Transactions on Graphics · doi:10.1145/3658207 · Cited by 9
On Finding Spherical Geodesic Paths and Circles in ℤ3
Biswas, R., & Bhowmick, P. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-09955-2_33 · Cited by 9
Practical Computation of the Cut Locus on Discrete Surfaces
Mancinelli, C., Livesu, M., & Puppo, E. (2021) · Computer Graphics Forum · doi:10.1111/cgf.14372 · Cited by 9
Curvature-based anisotropic geodesic distance computation for parametric and implicit surfaces
Seong, J., Jeong, W., & Cohen, E. (2009) · The Visual Computer · doi:10.1007/s00371-009-0362-0 · Cited by 9
Chapter 7 A survey of computational geometry
Mitchell, J. S. B., & Suri, S. (1995) · Handbooks in operations research and management science · doi:10.1016/s0927-0507(05)80124-0 · Cited by 9
Self-citationNuñez‐Garcia, M., Cámara, Ó., O'Neill, M. D., Razavi, R., Chubb, H., & Butakoff, C. (2018) · Medical Image Analysis · doi:10.1016/j.media.2018.10.001 · Cited by 9
GeodesicEmbedding (GE): A High-Dimensional Embedding Approach for Fast Geodesic Distance Queries
Xia, Q., Zhang, J., Fang, Z., Li, J., Zhang, M., Deng, B., & He, Y. (2021) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2021.3109975 · Cited by 9
Shortest paths on polyhedral surfaces and terrains
Cheng, S.-W., & Jin, J. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591821 · Cited by 9
Image and 3D-Object Editing with Precisely Specified Editing Regions
Bendels, G. H., Klein, R., Schilling, A., & Informatics, M. (2003) · Cited by 9
Sparse representation of step functions on manifolds
Melzi, S. (2019) · Computers & Graphics · doi:10.1016/j.cag.2019.05.010 · Cited by 9
Gross, B., Soltwedel, J. R., Shelton, E., Gomez, C. O., & Campàs, O. (2025) · Scientific Reports · doi:10.1038/s41598-025-13419-z · Cited by 9
Approximations of Geodesic Distances for Incomplete Triangular Manifolds
Azouz, Z. B., Bose, P. K., Shu, C., & Wuhrer, S. (2007) · Canadian Conference on Computational Geometry · Cited by 9
Standard Quasi-Conformal Flattening of the Right and Left Atria
Nuñez‐Garcia, M., Bernardino, G., Doste, R., Zhao, J., Cámara, Ó., & Butakoff, C. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-21949-9_10 · Cited by 9
Molenaar, M., & de Hoop, S. (1994) · Publications on geodesy. New series · doi:10.54419/gqn9oq · Cited by 9
Papadimitriou, C. H. (1986) · Lecture notes in computer science · doi:10.1007/3-540-17179-7_9 · Cited by 9
Self-citationAlgorithmic approaches to optimal route planning
Mitchell, J. S. B. (1991) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.25506 · Cited by 9
Self-citationMolecular architecture of thylakoid membranes within intact spinach chloroplastsPreprint
Wietrzyñski, W., Lamm, L., Wood, W. H., Loukeri, M.-J., Malone, L. A., Peng, T., Johnson, M. P., & Engel, B. D. (2025) · eLife · doi:10.7554/elife.105496.1 · Cited by 9
Molecular architecture of thylakoid membranes within intact spinach chloroplastsPreprint
Wietrzyñski, W., Lamm, L., Wood, W. H., Loukeri, M.-J., Malone, L. A., Peng, T., Johnson, M. P., & Engel, B. D. (2025) · eLife · doi:10.7554/elife.105496.2 · Cited by 9
Renso, F., Giacopini, M., Barbieri, S. G., & Mangeruga, V. (2023) · Proceedings of the Institution of Mechanical Engineers Part D Journal of Automobile Engineering · doi:10.1177/09544070231161909 · Cited by 8
On different topological classes of spherical geodesic paths and circles in Z3
Biswas, R., & Bhowmick, P. (2015) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.09.003 · Cited by 8
DE-Path: A Differential-Evolution-Based Method for Computing Energy-Minimizing Paths on Surfaces
Ye, Z., Liu, Y., Zheng, J., Hormann, K., & He, Y. (2019) · Computer-Aided Design · doi:10.1016/j.cad.2019.05.025 · Cited by 8
Computing the Riemannian center of mass on meshes
Mancinelli, C., & Puppo, E. (2023) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2023.102203 · Cited by 8
Pu, Y., Du, W.-C., Huang, C., & Lai, C.-K. (2012) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2012.03.065 · Cited by 8
Liu, Y., Xu, C., He, Y., & Kim, D. (2014) · Canadian Conference on Computational Geometry · Cited by 8
Geodesic Hermite Spline Curve on Triangular Meshes
Ha, Y., Park, J., & Yoon, S. (2021) · Symmetry · doi:10.3390/sym13101936 · Cited by 8
MLS-based scalar fields over triangle meshes and their application in mesh processing
Jin, J., Garland, M., & Ramos, E. A. (2009) · ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D) · doi:10.1145/1507149.1507173 · Cited by 8
Ordered Line Integral Methods for Solving the Eikonal Equation
Potter, S. F., & Cameron, M. (2019) · Journal of Scientific Computing · doi:10.1007/s10915-019-01077-z · Cited by 8
On some problems of computational geometry and topology
Musin, O. R. (1992) · Lecture notes in mathematics · doi:10.1007/bfb0084715 · Cited by 8
Shortest polygonal paths in space
Burkard, R. E., Rote, G., Yao, E. Y., & Yu, Z. (1990) · Computing · doi:10.1007/bf02250584 · Cited by 8
Translucent Radiosity: Efficiently CombiningDiffuse Inter-Reflection andSubsurface Scattering
Sheng, Y., Shi, Y., Wang, L., & Narasimhan, S. G. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2013.256 · Cited by 8
Quad Layouts – Generation and Optimization of Conforming Quadrilateral Surface Partitions
Campen, M. (2014) · RWTH Publications (RWTH Aachen) · doi:10.2312/diss.201412673 · Cited by 8
Geodesic Centroidal Voronoi Tessellations: Theories, Algorithms and ApplicationsPreprint
Ye, Z., Yi, R., Yu, M., Liu, Y., & He, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.00523 · Cited by 8
Approximating the Riemannian Metric from Point Clouds via Manifold Moving Least SquaresPreprint
Sober, B., Ravier, R., & Daubechies, I. C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.09885 · Cited by 8
Contributions of connectional pathways to shaping Alzheimer’s disease pathologies
Bougacha, S., Roquet, D., Landeau, B., Saul, E., Naveau, M., Sherif, S., Bejanin, A., Dhénain, M., Raj, A., Vivien, D., et al. (2024) · Brain Communications · doi:10.1093/braincomms/fcae459 · Cited by 7
MeshDMP: Motion Planning on Discrete Manifolds Using Dynamic Movement Primitives
Vedove, M. D., Abu‐Dakka, F. J., Palopoli, L., Fontanelli, D., & Saveriano, M. (2025) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra55743.2025.11128556 · Cited by 7
Optimal Point-to-Point geodesic path generation on point clouds
Agathos, A., & Azariadis, P. N. (2023) · Computer-Aided Design · doi:10.1016/j.cad.2023.103552 · Cited by 7
Proximity Queries on Point Clouds using Rapid Construction Path Oracle
Yan, Y., & Wong, R. C.-W. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3639261 · Cited by 7
User controllable anisotropic shape distribution on 3D meshes
Wang, X., Le, T. H., Ying, X., Sun, Q., & He, Y. (2016) · Computational Visual Media · doi:10.1007/s41095-016-0057-1 · Cited by 7
Part-in-whole matching of rigid 3D shapes using geodesic disk spectrum
Du, G., Yin, C., Zhou, M., Wu, Z., & Duan, F. (2017) · Multimedia Tools and Applications · doi:10.1007/s11042-017-5315-4 · Cited by 7
Research on GMAW based non-supporting thin-wall structure manufacturing
Liu, B., Shen, H., Deng, R., Zhou, Z., Jin, J., & Fu, J. (2020) · Rapid Prototyping Journal · doi:10.1108/rpj-05-2020-0102 · Cited by 7
Chen, Z., Tang, K., & Joneja, A. (2012) · Computer-Aided Design and Applications · doi:10.3722/cadaps.2013.321-337 · Cited by 7
Freeform modeling of faulted surfaces in seismic images
Parks, D. (2009) · Second International Meeting for Applied Geoscience & Energy · doi:10.1190/1.3255409 · Cited by 7
Generating Chinese Calligraphy on Freeform Shapes
Fu, Q., Wu, Z., Ying, X., Wang, M., Zheng, X., & Zhou, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53090-0_4 · Cited by 7
SpectroMeter: Amortized Sublinear Spectral Approximation of Distance on Graphs
Litman, R., & Bronstein, A. M. (2016) · International Conference on 3D Vision (3DV) · doi:10.1109/3dv.2016.60 · Cited by 7
Klein, R., Seidel, R., Teller, S. J., (hagen, R. K., & (saarbrucken, R. S. (2014) · CRC Press eBooks · doi:10.1201/b17041-12 · Cited by 7
A fast propagation scheme for approximate geodesic paths
Han, X., Yu, H., Yu, Y., & Zhang, J. (2017) · Graphical Models · doi:10.1016/j.gmod.2017.02.004 · Cited by 7
Adikusuma, Y. Y., Du, J., Fang, Z., & He, Y. (2022) · Computer-Aided Design · doi:10.1016/j.cad.2022.103333 · Cited by 7
Anisotropic geodesic distance computation for parametric surfaces
Seong, J., Jeong, W., & Cohen, E. (2008) · IEEE International Conference on Shape Modeling and Applications · doi:10.1109/smi.2008.4547968 · Cited by 7
Facility Location on a Polyhedral Surface
Aronov, B. S., van Kreveld, M. J., van Oostrum, R., & Varadarajan, K. (2003) · Discrete & Computational Geometry · doi:10.1007/s00454-003-2769-0 · Cited by 7
Computing Minimal Distances on Arbitrary Polyhedral Surfaces
Schwartz, E. (1987) · Defense Technical Information Center (DTIC) · doi:10.21236/ada210015 · Cited by 7
An Integrated Approach to Real-Time 3D Sensor Data Visualization for Digital Twin Applications
Kim, H., & Suh, H. (2025) · Electronics · doi:10.3390/electronics14152938 · Cited by 6
Deep Accurate Solver for the Geodesic Problem
Huberman, S., Bracha, A., & Kimmel, R. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-31975-4_22 · Cited by 6
Bulut, V., Onan, A., & Şenyayla, B. (2024) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2024.108821 · Cited by 6
Scalable shortest paths browsing on land surface
Xing, S., & Shahabi, C. (2010) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1869790.1869806 · Cited by 6
An improved algorithm for the shortest descending path on a convex terrain
Wei, X., & Joneja, A. (2012) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2012.12.001 · Cited by 6
Efficient Calculation of Distance Transform on Discrete Global Grid Systems
Kazemi, M., Wecker, L., & Samavati, F. F. (2022) · ISPRS International Journal of Geo-Information · doi:10.3390/ijgi11060322 · Cited by 6
EAR-Oracle: On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain Surface
Huang, B., Wei, V. J., Wong, R. C.-W., & Tang, B. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3588694 · Cited by 6
A 3D modeling and measurement system for cultural heritage preservation
Du, G., Zhou, M., Ren, P., Shui, W., Zhou, P., & Wu, Z. (2015) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.2189616 · Cited by 6
Short-Cuts on Star, Source and Planar Unfoldings
Chandru, V., Hariharan, R., & KrishnaKumar, N. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30538-5_15 · Cited by 6
Approximate straightest path computation and its application in parameterization
Li, Z., Jin, Y., Jin, X., & Ma, L. (2011) · The Visual Computer · doi:10.1007/s00371-011-0600-0 · Cited by 6
Asymptotically Optimal Feedback Planning: FMM Meets Adaptive Mesh Refinement
Yershov, D. S., & Frazzoli, E. (2015) · Springer tracts in advanced robotics · doi:10.1007/978-3-319-16595-0_40 · Cited by 6
Digital Surface Regularization With Guarantees
Cœurjolly, D., Lachaud, J., & Gueth, P. (2021) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2021.3055242 · Cited by 6
Proximity Queries on Terrain Surface
Wei, V. J., Wong, R. C.-W., Long, C., Mount, D. M., & Samet, H. (2022) · ACM Transactions on Database Systems · doi:10.1145/3563773 · Cited by 6
Self-citationShortest Paths along a Sequence of Line Segments in Euclidean Spaces
Hai, N. N., An, P. T., & Huyen, P. T. T. (2019) · Journal of convex analysis · doi:10.68381/jca26060 · Cited by 6
3D scan-based animation techniques for Chinese opera facial expression documentation
Zhou, H., & Mudur, S. P. (2007) · Computers & Graphics · doi:10.1016/j.cag.2007.08.005 · Cited by 6
Discrete Lagrangian algorithm for finding geodesics on triangular meshes
Remešíková, M., Šagát, M., & Novýsedlák, P. (2019) · Applied Mathematical Modelling · doi:10.1016/j.apm.2019.06.013 · Cited by 6
On the Vertex-oriented Triangle Propagation (VTP) Algorithm: Parallelization and Approximation
Du, J., He, Y., Fang, Z., Meng, W., & Xin, S. (2020) · Computer-Aided Design · doi:10.1016/j.cad.2020.102943 · Cited by 6
Computer aided design of ventilation tubes for customized hearing aid devices
Azernikov, S. (2009) · Computer-Aided Design · doi:10.1016/j.cad.2009.02.015 · Cited by 6
Constrained optimization with energy-minimizing curves and curve networks: a survey
Höfer, M. (2007) · Spring Conference on Computer Graphics · doi:10.1145/2614348.2614353 · Cited by 6
Unsupervised Identification of Coherent Motion in Video
da Silva, L. S., & Scharcanski, J. (2007) · Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI) · doi:10.1109/sibgrapi.2007.19 · Cited by 6
Approximate on‐Surface Distance Computation using Quasi‐Developable Charts
Torchelsen, R., Pinto, F., Bastos, R., & Comba, J. L. D. (2009) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2009.01555.x · Cited by 6
On quality paths on polyhedral terrains
van Kreveld, M. J. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58795-0_40 · Cited by 6
Geometric algorithms for geographic information systems
van Oostrum, R. (1999) · Utrecht University Repository (Utrecht University) · Cited by 6
Myelination across cortical hierarchies and depths in humans and macaquesPreprint
Nishio, M., Liu, X., Mackey, A. P., & Arcaro, M. J. (2025) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2025.02.06.636851 · Cited by 6
Génération et optimisation de trajectoire dans la fabrication additive par soudage à l'arc
Diourté, A. (2021) · theses.fr (ABES) · doi:10.70675/b6861eddz2af7z4f47za3abzf5bdd96e1d34 · Cited by 6
Efficient generation of geodesic random fields in finite elements with application to shell buckling
van den Broek, S. F., Jansen, E., & Rolfes, R. (2022) · Thin-Walled Structures · doi:10.1016/j.tws.2022.109646 · Cited by 5
Convex Quadratic Programming for Computing Geodesic Distances on Triangle Meshes
Chen, S., Hei, N., Hu, S., Yue, Z., & He, Y. (2024) · Mathematics · doi:10.3390/math12070993 · Cited by 5
Humans have a longer period of cortical maturation across depth and hierarchy than macaques
Nishio, M., Liu, X., Mackey, A. P., & Arcaro, M. J. (2025) · PLoS Biology · doi:10.1371/journal.pbio.3003378 · Cited by 5
Parallel Post-Processing of Restricted Voronoi Diagram on Thin Sheet Models
Zong, C., Wang, P., Yan, D.-M., Chen, S., Xin, S., Tu, C., & Hu, Q. (2022) · Computer-Aided Design · doi:10.1016/j.cad.2023.103511 · Cited by 5
curvedSpaceSim: A framework for simulating particles interacting along geodesics
Webb, T. H., & Sussman, D. M. (2025) · Computer Physics Communications · doi:10.1016/j.cpc.2025.109545 · Cited by 5
GeoMM: On Geodesic Perspective for Multi-modal Learning
Mei, S., Wang, H., & Ni, B. (2025) · 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/cvpr52734.2025.00450 · Cited by 5
ZhongKe, W. U., Liu, Y., ShiQing, X. I. N., MingQuan, Z. H. O. U., Ying, H. E., JunLi, Z. H. A. O., & XingCe, W. A. N. G. (2015) · Scientia Sinica Informationis · doi:10.1360/n112014-00018 · Cited by 5
Constrained Path Planning on Pipeline Surface for Wall Climbing Robots
Li, H., Liao, J., Zhu, S., Ge, H., Song, W., Chen, X., & Gu, J. J. (2022) · IEEE International Conference on Robotics and Biomimetics (ROBIO) · doi:10.1109/robio55434.2022.10011828 · Cited by 5
Furlan, V., Insero, F., & Giberti, H. (2025) · Rapid Prototyping Journal · doi:10.1108/rpj-03-2024-0109 · Cited by 5
Landmark transfer with minimal graph
Mykhalchuk, V., Cordier, F., & Seo, H. (2013) · Computers & Graphics · doi:10.1016/j.cag.2013.04.005 · Cited by 5
Pursuit Evasion on Polyhedral Surfaces
Klein, K., & Suri, S. (2015) · Algorithmica · doi:10.1007/s00453-015-9988-7 · Cited by 5
A Framework for Working with Digitized Cultural Heritage Artifacts
Özmen, C., & Balcisoy, S. S. (2006) · Lecture notes in computer science · doi:10.1007/11902140_43 · Cited by 5
Intrinsic Girth Function for Shape Processing
Xin, S., Wang, W., Chen, S., Zhao, J., & Shu, Z. (2016) · ACM Transactions on Graphics · doi:10.1145/2866570 · Cited by 5
Numerical Computation of Geodesics on Combined Piecewise-Smooth Surfaces
Caplan, R. M., Davis, M. W., Dehner, J., Hooper, N. R., Mattie, H., & Nadim, A. (2009) · Cited by 5
Haustral Fold Segmentation of CT Colonography Using Ridge Line Detection
Zhu, H., Li, L. C., Fan, Y., & Liang, Z. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25719-3_4 · Cited by 5
Approximating generalized distance functions on weighted triangulated surfaces with applications
Fort, M., & Sellarès, J. A. (2012) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2012.03.028 · Cited by 5
The Simulation of Delineation and Splitting in Virtual Liver Surgery
Shi, Y., Liu, M., Xiong, Y., Cai, C., Tan, K., & Pan, X. (2015) · International Conference on Virtual Reality and Visualization · doi:10.1109/icvrv.2015.44 · Cited by 5
GEODESIC COMPUTATION ON IMPLICIT SURFACES
Yu, H., & Zhang, J. (2010) · Bournemouth University Research Online (Bournemouth University) · Cited by 5
On the Expected Complexity of Voronoi Diagrams on Terrains
Driemel, A., Har-Peled, S., & Raichel, B. (2016) · ACM Transactions on Algorithms · doi:10.1145/2846099 · Cited by 5
Lightweight preprocessing and fast query of geodesic distance via proximity graph
Xin, S., Wang, W., He, Y., Zhou, Y., Chen, S., Tu, C., & Shu, Z. (2018) · Computer-Aided Design · doi:10.1016/j.cad.2018.04.021 · Cited by 5
Template-Guided 3D Fragment Reassembly Using GDS
Yin, C., Zhou, M., Fan, Y., & Shui, W. (2018) · Communications in computer and information science · doi:10.1007/978-981-13-1702-6_43 · Cited by 5
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.