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 301–400 of 807
geoTangle : Interactive Design of Geodesic Tangle Patterns on Surfaces
Nazzaro, G., Puppo, E., & Pellacini, F. (2021) · ACM Transactions on Graphics · doi:10.1145/3487909 · Cited by 17
King, N. D., Su, H., Aanjaneya, M., Ruuth, S. J., & Batty, C. (2024) · ACM Transactions on Graphics · doi:10.1145/3673652 · Cited by 17
Shortest paths and convex hulls in 2D complexes with non-positive curvature
Lubiw, A., Maftuleac, D., & Owen, M. (2020) · Computational Geometry · doi:10.1016/j.comgeo.2020.101626 · Cited by 17
Fast Quasi-Conformal Regional Flattening of the Left Atrium
Nuñez‐Garcia, M., Bernardino, G., Alarcón, F., Caixal, G., Mont, L., Cámara, Ó., & Butakoff, C. (2020) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2020.2966702 · Cited by 17
A Geometrical Method for Low-Dimensional Representations of Simulations
Iza-Teran, R., & Garcke, J. (2019) · SIAM/ASA Journal on Uncertainty Quantification · doi:10.1137/17m1154205 · Cited by 17
3D wave-equation dispersion inversion of surface waves recorded on irregular topography
Liu, Z., Li, J., Hanafy, S. M., Lu, K., & Schuster, G. T. (2020) · Geophysics · doi:10.1190/geo2019-0537.1 · Cited by 17
An Interactive Geometric Technique for Upper and Lower Teeth Segmentation
Le, B. H., Deng, Z., Xia, J. J., Chang, Y.-B., & Zhou, X. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04271-3_117 · Cited by 17
Yershov, D. S., & Frazzoli, E. (2015) · The International Journal of Robotics Research · doi:10.1177/0278364915602958 · Cited by 17
CONSTRUCTING THE CITY VORONOI DIAGRAM FASTER
Görke, R., Shin, C.-S., & Wolff, A. (2008) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195908002623 · Cited by 17
Shortest monotone descent path problem in polyhedral terrain
Roy, S., Das, S., & Nandy, S. C. (2006) · Computational Geometry · doi:10.1016/j.comgeo.2006.06.003 · Cited by 17
Contact Edit: Artist Tools for Intuitive Modeling of Hand-Object Interactions
Lakshmipathy, A., Feng, N., Lee, Y. X., Mahler, M., & Pollard, N. S. (2023) · ACM Transactions on Graphics · doi:10.1145/3592117 · Cited by 16
NeuroGF: A Neural Representation for Fast Geodesic Distance and Path Queries
Zhang, Q., Hou, J., Adikusuma, Y. Y., Wang, W., & He, Y. (2023) · neural information processing systems · doi:10.52202/075280-0855 · Cited by 16
A numerical simulation of neural fields on curved geometries
Martin, R., Chappell, D. J., Chuzhanova, N. A., & Crofts, J. J. (2018) · Journal of Computational Neuroscience · doi:10.1007/s10827-018-0697-5 · Cited by 16
Shortest Paths Among Obstacles in the Plane Revisited
Wang, H. (2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976465.51 · Cited by 16
Geodesic Distance Computation via Virtual Source Propagation
Trettner, P., Bommes, D., & Kobbelt, L. P. (2021) · Computer Graphics Forum · doi:10.1111/cgf.14371 · Cited by 16
Identifying sources of human interictal discharges with travelling wave and white matter propagation
Withers, C. P., Diamond, J. M., Yang, B., Snyder, K. M., Abdollahi, S., Sarlls, J. E., Chapeton, J. I., Theodore, W. H., Zaghloul, K. A., & Inati, S. K. (2023) · Brain · doi:10.1093/brain/awad259 · Cited by 16
A Method for Detection and Modeling of the Human Spine Based on Principal Curvatures
Santiesteban, Y., Sanchiz, J. M., & Sotoca, J. M. (2006) · Lecture notes in computer science · doi:10.1007/11892755_17 · Cited by 16
Higher-order Voronoi diagrams on triangulated surfaces
Cabello, S., Fort, M., & Sellarès, J. A. (2009) · Information Processing Letters · doi:10.1016/j.ipl.2009.01.001 · Cited by 16
Architecture of a surface exploration traverse analysis and navigational tool
Norheim, J. J., Hoffman, J. A., Newman, D. J., Cohen, T. E., Lees, D. S., Deans, M. C., & Lim, D. S. S. (2018) · IEEE Aerospace Conference (AERO) · doi:10.1109/aero.2018.8396510 · Cited by 16
Fast approximate geodesic paths on triangle mesh
Tang, J., Wu, G., Zhang, F., & Zhang, M. (2007) · Machine Intelligence Research · doi:10.1007/s11633-007-0008-5 · Cited by 16
An efficient algorithm for approximate Voronoi diagram construction on triangulated surfaces
Meng, W., Bo, P., Zhang, X., Hong, J., Xin, S., & Tu, C. (2023) · Computational Visual Media · doi:10.1007/s41095-022-0326-0 · Cited by 15
μMatch: 3D Shape Correspondence for Biological Image Data
Klatzow, J., Dalmasso, G., Martínez‐Abadías, N., Sharpe, J. A., & Uhlmann, V. (2022) · Frontiers in Computer Science · doi:10.3389/fcomp.2022.777615 · Cited by 15
Krogh, C., Hermansen, S. M., Lund, E. G., Kepler, J., & Jakobsen, J. (2023) · Composites Part A Applied Science and Manufacturing · doi:10.1016/j.compositesa.2023.107599 · Cited by 15
Geometric triangulations and discrete Laplacians on manifolds: An update
Glickenstein, D. A. (2023) · Computational Geometry · doi:10.1016/j.comgeo.2023.102063 · Cited by 15
3D Facial Similarity Measure Based on Geodesic Network and Curvatures
Zhao, J., Liu, C., Wu, Z., Duan, F., Zhang, M., Wang, K., & Jia, T. (2014) · Mathematical Problems in Engineering · doi:10.1155/2014/832837 · Cited by 15
How to walk your dog in the mountains with no magic leash
Har-Peled, S., Nayyeri, A., Salavatipour, M. R., & Sidiropoulos, A. (2012) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/2261250.2261269 · Cited by 15
The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains
Aronov, B. S., de Berg, M., & Thite, S. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87744-8_9 · Cited by 15
An Optimal-Time Algorithm for Shortest Paths on Realistic Polyhedra
Schreiber, Y. (2009) · Discrete & Computational Geometry · doi:10.1007/s00454-009-9136-8 · Cited by 15
Computing geodesic spectra of surfaces
Jin, M., Luo, F., Yau, S., & Gu, X. D. (2007) · ACM Symposium on Solid and Physical Modeling (SPM) · doi:10.1145/1236246.1236302 · Cited by 15
Shortest descending paths through given faces
Ahmed, M., & Lubiw, A. (2008) · Computational Geometry · doi:10.1016/j.comgeo.2007.10.011 · Cited by 15
Mesh editing with an embedded network of curves
Li, W. C., Lévy, B., & Paul, J. (2006) · IEEE International Conference on Shape Modeling and Applications · doi:10.1109/smi.2005.29 · Cited by 15
Aronov, B. S., van Kreveld, M. J., van Oostrum, R., & Varadarajan, K. (1998) · Lecture notes in computer science · doi:10.1007/3-540-49381-6_4 · Cited by 15
Fast and Memory‐Efficient Voronoi Diagram Construction on Triangle Meshes
Qin, Y., Yu, H., & Zhang, J. (2017) · Computer Graphics Forum · doi:10.1111/cgf.13248 · Cited by 14
Efficient Computation of Smoothed Exponential Maps
Herholz, P., & Alexa, M. (2019) · Computer Graphics Forum · doi:10.1111/cgf.13607 · Cited by 14
Liang, Y., Ren, X., & Feng, D. (2022) · International Journal of Pressure Vessels and Piping · doi:10.1016/j.ijpvp.2022.104813 · Cited by 14
ReMatching: Low-Resolution Representations for Scalable Shape Correspondence
Maggioli, F., Baieri, D., Rodolà, E., & Melzi, S. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-72913-3_11 · Cited by 14
3D Face Similarity Measure by Fréchet Distances of Geodesics
Zhao, J., Wu, Z., Pan, Z., Duan, F., Li, J., Lv, Z., Wang, K., & Chen, Y.-C. (2018) · Journal of Computer Science and Technology · doi:10.1007/s11390-018-1814-7 · Cited by 14
A new computational tool for liquid composite moulding process design based on configuration spaces
Montés, N., & Sánchez, F. (2009) · Composites Part A Applied Science and Manufacturing · doi:10.1016/j.compositesa.2009.07.003 · Cited by 14
A Whole Surface Approach to Crowd Simulation on Arbitrary Topologies
Ricks, B., & Egbert, P. K. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2013.110 · Cited by 14
Digital image approach to tool path generation for surface machining
Xu, K., & Li, Y. (2018) · The International Journal of Advanced Manufacturing Technology · doi:10.1007/s00170-018-3118-z · Cited by 14
Towards optimal path computation in a simplicial complex
Bhattacharya, S. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364919855422 · Cited by 14
A procedure to average 3D anatomical structures
Subramanyan, K., & Dean, D. (2000) · Medical Image Analysis · doi:10.1016/s1361-8415(00)00031-1 · Cited by 14
GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST
WANG, P., Krishnamurti, R., & Gupta, K. K. (2010) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195910003232 · Cited by 14
Optimistic Shortest Paths on Uncertain Terrains
Gray, C., & Evans, W. (2004) · Canadian Conference on Computational Geometry · Cited by 14
Three‐stage non‐Gaussian homogeneous random field representation over manifolds
Liang, Y., Feng, D., Ren, X., & Li, J. (2022) · Computer-Aided Civil and Infrastructure Engineering · doi:10.1111/mice.12959 · Cited by 13
ProSIP: Probabilistic Surface Interaction Primitives for Learning of Robotic Cleaning of Edges
Unger, C., Hartl-Nesic, C., Vu, M. N., & Kugi, A. (2024) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros58592.2024.10802255 · Cited by 13
Laplace-Beltrami Operator for Gaussian Splatting
Zhou, H., & Lähner, Z. (2026) · International Conference on 3D Vision (3DV) · doi:10.1109/3dv69130.2026.00110 · Cited by 13
The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces
Liu, Y., & Tang, K. (2013) · Information Processing Letters · doi:10.1016/j.ipl.2012.12.010 · Cited by 13
Topology-preserving smoothing of retinotopic maps
Tu, Y., Ta, D., Lu, Z., & Wang, Y. (2021) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1009216 · Cited by 13
Geodesic Tracks: Computing Discrete Geodesics With Track-Based Steiner Point Propagation
Meng, W., Xin, S., Tu, C., Chen, S., He, Y., & Wang, W. (2021) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2021.3109042 · Cited by 13
Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
Koehl, P., Delarue, M. H., & Orland, H. (2023) · Algorithms · doi:10.3390/a16030131 · Cited by 13
Farias, R., & Kallmann, M. (2019) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2019.2904271 · Cited by 13
Computing Smooth Quasi-geodesic Distance Field (QGDF) with Quadratic Programming
Cao, L., Zhao, J., Xu, J. H., Chen, S., Liu, G., Xin, S., Zhou, Y., & He, Y. (2020) · Computer-Aided Design · doi:10.1016/j.cad.2020.102879 · Cited by 13
Conjugate Product Graphs for Globally Optimal 2D-3D Shape Matching
Roetzer, P., Lähner, Z., & Bernard, F. (2023) · 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/cvpr52729.2023.02094 · Cited by 13
An intrinsic algorithm for computing geodesic distance fields on triangle meshes with holes
Quynh, D. T. P., He, Y., Xin, S., & Chen, Z. (2012) · Graphical Models · doi:10.1016/j.gmod.2012.04.009 · Cited by 13
Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon
Burago, D., Grigoriev, D. Y., & Slissenko, A. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.01.014 · Cited by 13
Dislocation screening in crystals with spherical topology
García-Aguilar, I., Fonda, P., & Giomi, L. (2020) · Physical review. E · doi:10.1103/physreve.101.063005 · Cited by 13
Craniofacial reconstruction based on heat flow geodesic grid regression (HF-GGR) model
Jia, B., Zhao, J., Xin, S., Duan, F., Pan, Z., Wu, Z., Li, J., & Zhou, M. (2021) · Computers & Graphics · doi:10.1016/j.cag.2021.04.029 · Cited by 13
Expansion-Based Algorithms for Finding Single Pair Shortest Path on Surface
Deng, K., & Zhou, X. (2005) · Lecture notes in computer science · doi:10.1007/11427865_12 · Cited by 13
Shortest paths on realistic polyhedra
Schreiber, Y. (2007) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1247069.1247081 · Cited by 13
Pursuit Evasion on Polyhedral Surfaces
Klein, K., & Suri, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-45030-3_27 · Cited by 12
A Convex Optimization Framework for Regularized Geodesic Distances
Edelstein, M., Guillen, N., Solomon, J., & Ben‐Chen, M. (2023) · ACM SIGGRAPH Conference (SIGGRAPH) · doi:10.1145/3588432.3591523 · Cited by 12
Euclidean Geodesic Loops on High-Genus Surfaces Applied to the Morphometry of Vestibular Systems
Xin, S., He, Y., Fu, C., Wang, D., Lin, S., Chu, C. W., Cheng, J. C. Y., Gu, X. D., & Lui, L. M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23629-7_47 · Cited by 12
A boundary focused quadrilateral mesh generation algorithm for multi-material structures
Liu, Y.-J., & Xing, H. (2012) · Journal of Computational Physics · doi:10.1016/j.jcp.2012.08.042 · Cited by 12
How to Walk Your Dog in the Mountains with No Magic Leash
Har-Peled, S., Nayyeri, A., Salavatipour, M. R., & Sidiropoulos, A. (2015) · Discrete & Computational Geometry · doi:10.1007/s00454-015-9737-3 · Cited by 12
Distance Oracle on Terrain Surface
Wei, V. J., Wong, R. C.-W., Long, C., & Mount, D. M. (2017) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3035918.3064038 · Cited by 12
Self-citationApproximate Shortest Descending Paths
Cheng, S.-W., & Jin, J. (2014) · SIAM Journal on Computing · doi:10.1137/130913808 · Cited by 12
SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM
Ahmed, M., & Lubiw, A. (2011) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195911003755 · Cited by 12
Solving the initial value problem of discrete geodesics
Cheng, P., Miao, C., Liu, Y., Tu, C., & He, Y. (2015) · Computer-Aided Design · doi:10.1016/j.cad.2015.07.012 · Cited by 12
Smooth Polylines on Polygon Meshes
Bonneau, G., & Hahmann, S. (2004) · Mathematics and visualization · doi:10.1007/978-3-662-07443-5_5 · Cited by 12
Near-Minimum-Energy Paths on a Vertical-Axis Cone With Anisotropic Friction and Gravity Effects
Rowe, N. C., & Kanayama, Y. J. (1994) · The International Journal of Robotics Research · doi:10.1177/027836499401300503 · Cited by 12
Shortest Path Problems on a Polyhedral Surface
Cook, A. F., & Wenk, C. (2012) · Algorithmica · doi:10.1007/s00453-012-9723-6 · Cited by 12
Determining data independence on a digitized membrane in three dimensions
Lifshitz, L. M. (1998) · IEEE Transactions on Medical Imaging · doi:10.1109/42.700742 · Cited by 12
Laser path calculation method on triangulated mesh for repair process on turbine parts
Yuan, L., Bobek, T., & Klocke, F. (2015) · Computer-Aided Design · doi:10.1016/j.cad.2015.04.009 · Cited by 12
A Variational Framework for Computing Geodesic Paths on Sweep Surfaces
Meng, W., Xin, S., Zhao, J., Chen, S., Tu, C., & He, Y. (2021) · Computer-Aided Design · doi:10.1016/j.cad.2021.103077 · Cited by 11
Extracting a functional representation from a dictionary for non-rigid shape matching
Colombo, M., Boracchi, G., & Melzi, S. (2023) · Computers & Graphics · doi:10.1016/j.cag.2023.04.010 · Cited by 11
Differentiable Geodesic Distance for Intrinsic Minimization on Triangle Meshes
Li, Y., Numerow, L., Thomaszewski, B., & Coros, S. (2024) · ACM Transactions on Graphics · doi:10.1145/3658122 · Cited by 11
A practical analytic model for the radiosity of translucent scenes
Sheng, Y., Shi, Y., Wang, L., & Narasimhan, S. G. (2013) · ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D) · doi:10.1145/2448196.2448206 · Cited by 11
Parallelizing discrete geodesic algorithms with perfect efficiency
Ying, X., Huang, C., Fu, X., He, Y., Yu, R., Wang, J., & Yu, M. (2019) · Computer-Aided Design · doi:10.1016/j.cad.2019.05.023 · Cited by 11
A Variational Framework for Curve Shortening in Various Geometric Domains
Yuan, N., Wang, P., Meng, W., Chen, S., Xu, J. F., Xin, S., He, Y., & Wang, W. (2021) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2021.3135021 · Cited by 11
Width-bounded geodesic strips for surface tiling
Kahlert, J., Olson, M., & Zhang, H. (2010) · The Visual Computer · doi:10.1007/s00371-010-0513-3 · Cited by 11
A Triangulation-Invariant Method for Anisotropic Geodesic Map Computation on Surface Meshes
Yoo, S. W., Seong, J., Sung, M., Shin, S. Y., & Cohen, E. (2012) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2012.29 · Cited by 11
TOWARDS A 3D BASED PLATFORM FOR CULTURAL HERITAGE SITE SURVEY AND VIRTUAL EXPLORATION
Seinturier, J., Riedinger, C., Mahiddine, A., Peloso, D., Boï, J.-M., Merad, D., & Drap, P. (2013) · The international archives of the photogrammetry, remote sensing and spatial information sciences/International archives of the photogrammetry, remote sensing and spatial information sciences · doi:10.5194/isprsarchives-xl-5-w2-573-2013 · Cited by 11
Multiple shooting approach for computing approximately shortest paths on convex polytopes
Hoài, T. V., An, P. T., & Hải, N. N. (2016) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2016.10.026 · Cited by 11
Self-similar slip distributions on irregular shaped faults
Herrero, A., & Murphy, S. (2018) · Geophysical Journal International · doi:10.1093/gji/ggy104 · Cited by 11
Cao, P., Fan, Z., Gao, R. X., & Tang, J. (2018) · Journal of Manufacturing Science and Engineering · doi:10.1115/1.4040320 · Cited by 11
Straightest Paths on Meshes by Cutting Planes
Lee, S., Han, J.-H., & Lee, H. (2006) · Lecture notes in computer science · doi:10.1007/11802914_47 · Cited by 11
Rigid body dynamics simulation for robot motion planning
Ettlin, A. (2006) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-3663 · Cited by 11
Garment Avatars: Realistic Cloth Driving using Pattern RegistrationPreprint
Halimi, O., Prada, F., Stuyck, T., Xiang, D., Bagautdinov, T., He, W., Kimmel, R., Shiratori, T., Wu, C., & Sheikh, Y. A. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.03373 · Cited by 11
Exact Voronoi diagram for topographic spatial analysis
Duan, X., Li, L., Ge, Y., & Liu, B. (2023) · GIScience & Remote Sensing · doi:10.1080/15481603.2023.2171703 · Cited by 10
Splines on manifolds: A survey
Mancinelli, C., & Puppo, E. (2024) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2024.102349 · Cited by 10
Craniofacial Reconstruction Evaluation by Geodesic Network
Zhao, J., Liu, C., Wu, Z., Duan, F., Wang, K., Jia, T., & Liu, Q. (2014) · Computational and Mathematical Methods in Medicine · doi:10.1155/2014/943647 · Cited by 10
Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves
An, P. T. (2017) · Optimization · doi:10.1080/02331934.2017.1387260 · Cited by 10
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.6048681 · Cited by 10
Surface roughness in finite-element meshes: application to plasmonic nanostructures
Loth, F., Kiel, T., Busch, K., & Kristensen, P. T. (2022) · Journal of the Optical Society of America B · doi:10.1364/josab.476883 · Cited by 10
Kageura, M., & Shimada, K. (2004) · Journal of Mechanical Design · doi:10.1115/1.1814386 · Cited by 10
Storing the subdivision of a polyhedral surface
Mount, D. M. (1986) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/10515.10532 · Cited by 10
Self-citationAutomated Identification of Fiducial Points on 3D Torso Images
Kawale, M., Reece, G. P., Crosby, M. A., Beahm, E. K., Fingeret, M. C., Markey, M. K., & Merchant, F. A. (2013) · Biomedical Engineering and Computational Biology · doi:10.4137/becb.s11800 · Cited by 10
Reducing the memory required to find a geodesic shortest path on a large mesh
Verma, V., & Snoeyink, J. S. (2009) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1653771.1653804 · Cited by 10
Isotropic Mesh Simplification by Evolving the Geodesic Delaunay Triangulation
Xin, S., Chen, S., He, Y., Wang, G., Gu, X. D., & Qin, H. (2011) · International Symposium on Voronoi Diagrams in Science and Engineering · doi:10.1109/isvd.2011.14 · Cited by 10
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.