Shortest paths and convex hulls in 2D complexes with non-positive curvature
From MaRDI portal
Publication:2206723
Abstract: Globally non-positively curved, or CAT(0), polyhedral complexes arise in a number of applications, including evolutionary biology and robotics. These spaces have unique shortest paths and are composed of Euclidean polyhedra, yet many algorithms and properties of shortest paths and convex hulls in Euclidean space fail to transfer over. We give an algorithm, using linear programming, to compute the convex hull of a set of points in a 2-dimensional CAT(0) polyhedral complex with a single vertex. We explore the use of shortest path maps to answer single-source shortest path queries in 2-dimensional CAT(0) polyhedral complexes, and we unify efficient solutions for 2-manifold and rectangular cases.
Recommendations
- Shortest path problem in rectangular complexes of global nonpositive curvature
- ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
- Shortest path problems on a polyhedral surface
- SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
Cites work
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 3541764 (Why is no real title available?)
- scientific article; zbMATH DE number 1424303 (Why is no real title available?)
- A Panoramic View of Riemannian Geometry
- A new polynomial-time algorithm for linear programming
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- An optimal convex hull algorithm in any fixed dimension
- CAT(0) is an algorithmic property
- Computing geodesic distances in tree space
- Computing medians and means in Hadamard spaces
- Computing minimum length paths of a given homotopy class
- Confidence Sets for Phylogenetic Trees
- Convex analysis and optimization in Hadamard spaces
- Convexity in tree spaces
- Distance and routing labeling schemes for non-positively curved plane graphs
- Ends of Group Pairs and Non-Positively Curved Cube Complexes
- Euclidean shortest paths in the presence of rectilinear barriers
- Geodesics in CAT(0) cubical complexes
- Geometry of the space of phylogenetic trees
- Graphs of some CAT(0) complexes
- Horoball hulls and extents in positive definite space
- Limiting behaviour of Fréchet means in the space of phylogenetic trees
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Median graphs, parallelism and posets
- Network flows. Theory, algorithms, and applications.
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Optimal shortest path queries in a simple polygon
- Polyhedral computational geometry for averaging metric phylogenetic trees
- Polynomial algorithms in linear programming
- Principal component analysis and the locus of the Fréchet mean in the space of phylogenetic trees
- Relative convex hulls in semi-dynamic arrangements
- SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
- Shortest path problem in rectangular complexes of global nonpositive curvature
- Some results on the convex hull of finitely many convex sets
- Some results on the geometry of convex hulls in manifolds of pinched negative curvature
- Special cube complexes
- Statistical approach to tests involving phylogenies
- Storing the subdivision of a polyhedral surface
- The Discrete Geodesic Problem
- The Ultimate Planar Convex Hull Algorithm?
- The geometry and topology of reconfiguration
- The logarithm map, its limits and Fréchet means in orthant spaces
- The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
- Touring a sequence of polygons
- Triangulating a simple polygon in linear time
- Two algorithms for constructing a Delaunay triangulation
Cited in
(4)
This page was built for publication: Shortest paths and convex hulls in 2D complexes with non-positive curvature
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2206723)
