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 101–200 of 807
Parallel chen-han (PCH) algorithm for discrete geodesics
Ying, X., Xin, S., & He, Y. (2014) · ACM Transactions on Graphics · doi:10.1145/2534161 · Cited by 64
Optimal Any-Angle Pathfinding In Practice
Harabor, D., Grastien, A., Öz, D., & Aksakallı, V. (2016) · Journal of Artificial Intelligence Research · doi:10.1613/jair.5007 · Cited by 64
Liu, Y., Xu, C.-X., Yi, R., Fan, D., & He, Y. (2016) · ACM Transactions on Graphics · doi:10.1145/2980179.2982424 · Cited by 64
Facial Structure Analysis Separates Autism Spectrum Disorders into Meaningful Clinical Subgroups
Obafemi-Ajayi, T., Miles, J. H., Takahashi, T., Qi, W., Aldridge, K. J., Zhang, M., Xin, S.-Q., He, Y., & Duan, Y. (2014) · Journal of Autism and Developmental Disorders · doi:10.1007/s10803-014-2290-8 · Cited by 64
Constructing Approximate Shortest Path Maps in Three Dimensions
Har-Peled, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539797325223 · Cited by 64
Print Paths Key-framing: Design for non-planar layered robotic FDM printing
Mitropoulou, I., Bernhard, M., & Dillenburger, B. (2020) · ACM Symposium on Computational Fabrication (SCF) · doi:10.1145/3424630.3425408 · Cited by 63
On the Effectiveness of Persistent Homology
Turkeš, R., Montúfar, G., & Otter, N. (2022) · neural information processing systems · doi:10.52202/068431-2568 · Cited by 63
Algorithmic Motion Planning in Robotics
Schwartz, J. T., & Sharir, M. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50013-8 · Cited by 63
Efficient computation of Euclidean shortest paths in the plane
Hershberger, J. E., & Suri, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366836 · Cited by 62
Interactive Mesh Fusion Based on Local 3D Metamorphosis
Kanai, T., Suzuki, H., Mitani, J., & Kimura, F. (1999) · Proceedings · doi:10.20380/gi1999.20 · Cited by 62
Multivalued distance maps for motion planning on surfaces with moving obstacles
Kimmel, R., Kiryati, N., & Bruckstein, A. M. (1998) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.678452 · Cited by 62
Optimization of composite structures with curved fiber trajectories
Lemaire, E., Zein, S., & Bruyneel, M. (2015) · Composite Structures · doi:10.1016/j.compstruct.2015.06.040 · Cited by 61
Piecewise Regular Meshes: Construction and Compression
Szymczak, A., Rossignac, J. R., & King, D. (2002) · Graphical Models · doi:10.1006/gmod.2002.0577 · Cited by 61
An Optimal Any-Angle Pathfinding Algorithm
Harabor, D., & Grastien, A. (2013) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v23i1.13609 · Cited by 60
Montage4D: interactive seamless fusion of multiview video textures
Du, R., Chuang, M., Chang, W., Hoppe, H., & Varshney, A. (2018) · ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D) · doi:10.1145/3190834.3190843 · Cited by 60
Visibility graphs and obstacle-avoiding shortest paths
Alt, H. G., & Welzl, E. (1988) · Mathematical Methods of Operations Research · doi:10.1007/bf01928918 · Cited by 60
An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions
Schreiber, Y., & Sharir, M. (2007) · Discrete & Computational Geometry · doi:10.1007/s00454-007-9031-0 · Cited by 59
Practical methods for approximating shortest paths on a convex polytope in R3
Hershberger, J. E., & Suri, S. (1998) · Computational Geometry · doi:10.1016/s0925-7721(97)00004-7 · Cited by 58
Vekhter, J., Zhuo, J., Fandino, L. F. G., Huang, Q., & Vouga, E. (2019) · ACM Transactions on Graphics · doi:10.1145/3306346.3323043 · Cited by 57
Kanai, T., & Suzuki, H. (2000) · Geometric Modeling and Processing · doi:10.1109/gmap.2000.838256 · Cited by 57
Surface-Preserving Robust Watermarking of 3-D Shapes
Luo, M., & Bors, A. G. (2011) · IEEE Transactions on Image Processing · doi:10.1109/tip.2011.2142004 · Cited by 55
Random field simulation over curved surfaces: Applications to computational structural mechanics
Scarth, C., Adhikari, S., Cabral, P. H., Silva, G. H. C., & do Prado, A. P. (2018) · Computer Methods in Applied Mechanics and Engineering · doi:10.1016/j.cma.2018.10.026 · Cited by 55
Constant-time all-pairs geodesic distance query on triangle meshes
Xin, S., Ying, X., & He, Y. (2012) · ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D) · doi:10.1145/2159616.2159622 · Cited by 55
Ray-Tracing Model for Generalized Geodesic-Lens Multiple-Beam Antennas
Liao, Q., Fonseca, N. J. G., Camacho, M., Palomares‐Caballero, Á., Mesa, F., & Quevedo-Teruel, Ó. (2023) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2022.3233643 · Cited by 54
Campen, M., Heistermann, M., & Kobbelt, L. P. (2013) · Computer Graphics Forum · doi:10.1111/cgf.12173 · Cited by 54
Tracing Field‐Coherent Quad Layouts
Pietroni, N., Puppo, E., Marcias, G., Scopigno, R., & Cignoni, P. (2016) · Computer Graphics Forum · doi:10.1111/cgf.13045 · Cited by 54
REACTO: Reconstructing Articulated Objects from a Single Video
Song, C., Wei, J., Foo, C.-S., Lin, G., & Liu, F. (2024) · 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/cvpr52733.2024.00515 · Cited by 53
Automatic multi-resolution shape modeling of multi-organ structures
Cerrolaza, J. J., Reyes, M., Summers, R. M., Ballester, M. Á. G., & Linguraru, M. G. (2015) · Medical Image Analysis · doi:10.1016/j.media.2015.04.003 · Cited by 53
A functional-based segmentation of human body scans in arbitrary postures
Werghi, N., Xiao, Y., & Siebert, J. P. (2006) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2005.854503 · Cited by 53
The application of muscle wrapping to voxel-based finite element models of skeletal structures
Jia, L., Shi, J., Fitton, L. C., Phillips, R., O’Higgins, P., & Fagan, M. J. (2011) · Biomechanics and Modeling in Mechanobiology · doi:10.1007/s10237-011-0291-5 · Cited by 52
GeoNet: Deep Geodesic Networks for Point Cloud Analysis
He, T., Huang, H., Yi, L., Zhou, Y., Wu, C.-H., Wang, J., & Soatto, S. (2019) · 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/cvpr.2019.00705 · Cited by 52
On maximum flows in polyhedral domains
Mitchell, J. S. B. (1990) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(90)90020-l · Cited by 52
Self-citationPlanning and reasoning for autonomous vehicle control
Mitchell, J. S. B., Payton, D. W., & Keirsey, D. M. (1987) · International Journal of Intelligent Systems · doi:10.1002/int.4550020204 · Cited by 52
Self-citationOptimal transport on discrete domains
Solomon, J. (2020) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/076/05 · Cited by 51
Bijective and coarse high-order tetrahedral meshes
Jiang, Z., Zhang, Z., Hu, Y., Schneider, T., Zorin, D., & Panozzo, D. (2021) · ACM Transactions on Graphics · doi:10.1145/3450626.3459840 · Cited by 50
Computerized girth determination for custom footwear manufacture
Zhao, J., Xiong, S., Bu, Y., & Goonetilleke, R. S. (2007) · Computers & Industrial Engineering · doi:10.1016/j.cie.2007.07.015 · Cited by 50
Gomputing geodesic distances on triangular meshes
Novotni, M., & Klein, R. (2002) · Digital Library (University of West Bohemia) · Cited by 48
Barycentric Coordinates on Surfaces
Rustamov, R. M. (2010) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2010.01759.x · Cited by 48
Simplicial dijkstra and A* algorithms for optimal feedback planning
Yershov, D. S., & LaValle, S. M. (2011) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2011.6095032 · Cited by 48
Bijective projection in a shell
Jiang, Z., Schneider, T., Zorin, D., & Panozzo, D. (2020) · ACM Transactions on Graphics · doi:10.1145/3414685.3417769 · Cited by 47
Efficiently determining a locally exact shortest path on polyhedral surfaces
Xin, S., & Wang, G. (2007) · Computer-Aided Design · doi:10.1016/j.cad.2007.08.001 · Cited by 47
Computational surface flattening: a voxel-based approach
Grossmann, R., Kiryati, N., & Kimmel, R. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.993552 · Cited by 47
Surface Simplification using Intrinsic Error Metrics
Liu, H. D., Gillespie, M., Chislett, B., Sharp, N., Jacobson, A., & Crane, K. (2023) · ACM Transactions on Graphics · doi:10.1145/3592403 · Cited by 46
Iso-scallop tool path planning for triangular mesh surfaces in multi-axis machining
Liang, F., Kang, C., Lu, Z., & Fang, F. (2021) · Robotics and Computer-Integrated Manufacturing · doi:10.1016/j.rcim.2021.102206 · Cited by 46
Accurate Computation of Geodesic Distance Fields for Polygonal Curves on Triangle Meshes
Bommes, D., & Kobbelt, L. P. (2007) · RWTH Publications (RWTH Aachen) · Cited by 46
Fast geodesics computation with the phase flow method
Ying, L., & Candès, E. J. (2006) · Journal of Computational Physics · doi:10.1016/j.jcp.2006.07.032 · Cited by 46
Computing minimal distances on polyhedral surfaces
Wolfson, E., & Schwartz, E. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.35505 · Cited by 46
Integrating neuroinformatics tools in TheVirtualBrain
Woodman, M., Pézard, L., Domide, L., Knock, S. A., Sanz‐Leon, P., Mersmann, J., McIntosh, A. R., & Jirsa, V. (2014) · Frontiers in Neuroinformatics · doi:10.3389/fninf.2014.00036 · Cited by 45
Exact Geodesics and Shortest Paths on Polyhedral Surfaces
Balasubramanian, M., Polimeni, J. R., & Schwartz, E. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.213 · Cited by 45
Approximating weighted shortest paths on polyhedral surfaces
Lanthier, M. A., Maheshwari, A., & Sack, J.-R. (1997) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/262839.263101 · Cited by 45
Voronoi diagrams for direction-sensitive distances
Aichholzer, O., Chen, D. Z., Lee, D. T., Mukhopadhyay, A., Papadopoulou, E., & Aurenhammer, F. (1997) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/262839.263045 · Cited by 44
Long range attachments - a method to simulate inextensible clothing in computer games
Kim, T., Chentanez, N., & Müller, M. (2012) · Symposium on Computer Animation · doi:10.5555/2422356.2422399 · Cited by 44
Quantitative evaluation of three cortical surface flattening methods
Ju, L., Hurdal, M. K., Stern, J., Rehm, K., Schaper, K. A., & Rottenberg, D. A. (2005) · NeuroImage · doi:10.1016/j.neuroimage.2005.06.055 · Cited by 44
Approximating Shortest Paths on a Nonconvex Polyhedron
Varadarajan, K., & Agarwal, P. K. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539799352759 · Cited by 44
Deshpande, C., Kharade, A., Pandhare, A., Ghatekar, A., Gawade, S., & Kodati, V. (2009) · CRC Press eBooks · doi:10.1201/b15839-7 · Cited by 43
Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures
Liu, Y. (2012) · Computer-Aided Design · doi:10.1016/j.cad.2012.11.005 · Cited by 43
A Survey of Folding and Unfolding in Computational Geometry
Demaine, E. D., & O’Rourke, J. (2005) · Cambridge University Press eBooks · doi:10.1017/9781009701259.013 · Cited by 43
Path planning in the presence of vertical obstacles
Gewali, L. P., Ntafos, S. C., & Tollis, I. G. (1990) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.56665 · Cited by 43
Generation of Configuration Space Obstacles: Moving Algebraic Surfaces
Bajaj, C., & Kim, M. S. (1990) · The International Journal of Robotics Research · doi:10.1177/027836499000900104 · Cited by 43
3D surface imaging of the human female torso in upright to supine positions
Reece, G. P., Merchant, F. A., Andon, J., Khatam, H., Ravi‐Chandar, K., Weston, J., Fingeret, M. C., Lane, C., Duncan, K., & Markey, M. K. (2015) · Medical Engineering & Physics · doi:10.1016/j.medengphy.2015.01.011 · Cited by 42
Spatiotemporal organisation of human sensorimotor beta burst activity
Zich, C., Quinn, A. J., Bonaiuto, J. J., O’Neill, G. C., Mardell, L. C., Ward, N., & Bestmann, S. (2023) · eLife · doi:10.7554/elife.80160 · Cited by 41
Approximate Shortest Paths and Geodesic Diameter on a Convex Polytope in Three Dimensions
Har-Peled, S. (1999) · Discrete & Computational Geometry · doi:10.1007/pl00009417 · Cited by 41
Random fields representation over manifolds via isometric feature mapping‐based dimension reduction
Feng, D., Liang, Y., Ren, X., & Li, J. (2021) · Computer-Aided Civil and Infrastructure Engineering · doi:10.1111/mice.12752 · Cited by 40
Sublinear Geometric Algorithms
Chazelle, B., Liu, D., & Magen, A. (2005) · SIAM Journal on Computing · doi:10.1137/s009753970444572x · Cited by 40
Efficient piecewise-linear function approximation using the uniform metric
Goodrich, M. T. (1994) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/177424.178040 · Cited by 40
Motion planning in R/sup 3/ for multiple tethered robots
Hert, S., & Lumelsky, V. (1999) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.781966 · Cited by 40
Polyhedral Surfaces of Constant Mean Curvature
Polthier, K. (2002) · Cited by 40
Schwartz, E., Merker, B. H., Wolfson, E., & Shaw, A. (1988) · IEEE Computer Graphics and Applications · doi:10.1109/38.7745 · Cited by 40
Lubiw, A., Munro, I., & Demaine, E. D. (2002) · Cited by 40
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 · Cited by 40
CGAL: the computational geometry algorithms library
Alliez, P., & Fabri, A. (2016) · ACM SIGGRAPH Courses · doi:10.1145/2897826.2927362 · Cited by 39
Efficiently Computing Exact Geodesic Loops within Finite Steps
Xin, S.-Q., He, Y., & Fu, C. (2011) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2011.119 · Cited by 39
Continuous Shortest Path Vector Field Navigation on 3D Triangular Meshes for Mobile Robots
Pütz, S., Wiemann, T., Piening, M. K., & Hertzberg, J. (2021) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra48506.2021.9560981 · Cited by 38
Connectome spatial smoothing (CSS): Concepts, methods, and evaluation
Sina Mansour, L., Seguin, C., Smith, R. E., & Zalesky, A. (2022) · NeuroImage · doi:10.1016/j.neuroimage.2022.118930 · Cited by 38
A Heat Method for Generalized Signed Distance
Feng, N., & Crane, K. (2024) · ACM Transactions on Graphics · doi:10.1145/3658220 · Cited by 37
Constructing Intrinsic Delaunay Triangulations from the Dual of Geodesic Voronoi Diagrams
Liu, Y., Fan, D., Xu, C.-X., & He, Y. (2017) · ACM Transactions on Graphics · doi:10.1145/2999532 · Cited by 37
On the shortest paths between two convex polyhedra
Balstan, A., & Sharir, M. (1988) · Journal of the ACM · doi:10.1145/42282.214094 · Cited by 37
Analysis of flow and visibility on triangulated terrains
Tsirogiannis, K. (2011) · TU/e Research Portal · doi:10.6100/ir717789 · Cited by 37
Parallel and Scalable Heat Methods for Geodesic Distance Computation
Tao, J., Zhang, J., Deng, B., Fang, Z., Peng, Y., & He, Y. (2019) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2019.2933209 · Cited by 36
Approximation and exact algorithms for minimum-width annuli and shells
Agarwal, P. K., Aronov, B. S., Har-Peled, S., & Sharir, M. (1999) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/304893.304992 · Cited by 36
PICO: Reconstructing 3D People In Contact with Objects
Cseke, A., Tripathi, S., Dwivedi, S. K., Lakshmipathy, A., Chatterjee, A., Black, M. J., & Tzionas, D. (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.00173 · Cited by 35
Algorithms for Approximate Shortest Path Queries on Weighted Polyhedral Surfaces
Aleksandrov, L., Djidjev, H. N., Guo, H., Maheshwari, A., Nussbaum, D., & Sack, J.-R. (2009) · Discrete & Computational Geometry · doi:10.1007/s00454-009-9204-0 · Cited by 35
Anisotropic geodesics for live‐wire mesh segmentation
Zhuang, Y., Zou, M., Carr, N., & Ju, T. (2014) · Computer Graphics Forum · doi:10.1111/cgf.12479 · Cited by 35
Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
Wang, X., Fang, Z., Wu, J., Xin, S., & He, Y. (2017) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2017.03.010 · Cited by 35
Geographic representation in spatial analysis
Miller, H. J. (2000) · Journal of Geographical Systems · doi:10.1007/s101090050030 · Cited by 35
Kinematic Motion Retargeting for Contact-Rich Anthropomorphic Manipulations
Lakshmipathy, A., Hodgins, J. K., & Pollard, N. S. (2025) · ACM Transactions on Graphics · doi:10.1145/3723872 · Cited by 34
Agarwal, P. K., & Sharir, M. (2000) · Elsevier eBooks · doi:10.1016/b978-044482537-7/50002-4 · Cited by 34
Handling degenerate cases in exact geodesic computation on triangle meshes
Liu, Y., Zhou, Q.-Y., & Hu, S. (2007) · The Visual Computer · doi:10.1007/s00371-007-0136-5 · Cited by 34
Between shapes, using the Hausdorff distance
van Kreveld, M. J., Miltzow, T., Ophelders, T., Sonke, W., & Vermeulen, J. L. (2021) · Computational Geometry · doi:10.1016/j.comgeo.2021.101817 · Cited by 33
Hierarchical cortical gradients in somatosensory processing
Saadon‐Grosman, N., Arzy, S., & Loewenstein, Y. (2020) · NeuroImage · doi:10.1016/j.neuroimage.2020.117257 · Cited by 33
Path planning in 0/1/ weighted regions with applications
Gewali, L. P., Meng, A. C., Mitchell, J. S. B., & Ntafos, S. C. (1988) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/73393.73421 · Cited by 33
Self-citationComputing Approximate Shortest Paths on Convex Polytopes
Agarwal, P. K., Har-Peled, S., & Karia, M. (2002) · Algorithmica · doi:10.1007/s00453-001-0111-x · Cited by 33
A single-exponential upper bound for finding shortest paths in three dimensions
Reif, J. H., & Storer, J. A. (1994) · Journal of the ACM · doi:10.1145/185675.185811 · Cited by 33
Geodesic Paths On 3D Surfaces: Survey and Open ProblemsPreprint
Maheshwari, A., & Wuhrer, S. (2009) · NPARC · doi:10.4224/16931693 · Cited by 33
Haustral Fold Segmentation With Curvature-Guided Level Set Evolution
Zhu, H., Barish, M. A., Pickhardt, P. J., & Liang, Z. (2012) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2012.2226242 · Cited by 32
Rowe, N. C. (1997) · The International Journal of Robotics Research · doi:10.1177/027836499701600307 · Cited by 32
Optimal path finding in direction, location, and time dependent environments
Dolinskaya, I. (2012) · Naval Research Logistics (NRL) · doi:10.1002/nav.21492 · Cited by 32
Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings
Miller, E., & Pak, I. (2008) · Discrete & Computational Geometry · doi:10.1007/s00454-008-9052-3 · Cited by 32
Folding and Unfolding Linkages, Paper, and Polyhedra
Demaine, E. D. (2001) · Lecture notes in computer science · doi:10.1007/3-540-47738-1_9 · Cited by 32
An efficient three-dimensional face recognition system based random forest and geodesic curves
Nassih, B., Amine, A., Ngadi, M., Azdoud, Y., Naji, D., & Hmina, N. (2021) · Computational Geometry · doi:10.1016/j.comgeo.2021.101758 · Cited by 31
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.