Shortest paths and convex hulls in 2D complexes with non-positive curvature

DOI10.1016/J.COMGEO.2020.101626zbMATH Open1476.68289arXiv1603.00847OpenAlexW3006653235MaRDI QIDQ2206723FDOQ2206723

Daniela Maftuleac, Anna Lubiw, Megan Owen

Publication date: 23 October 2020

Published in: Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1603.00847

zbMATH Keywords

convex hullshortest pathCAT(0)polyhedral complex

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55) Polyhedral manifolds (52B70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new polynomial-time algorithm for linear programming
• Geometry of the space of phylogenetic trees
• Polyhedral computational geometry for averaging metric phylogenetic trees
• An optimal convex hull algorithm in any fixed dimension
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Graphs of some CAT(0) complexes
• Convex analysis and optimization in Hadamard spaces
• Polynomial algorithms in linear programming
• A Panoramic View of Riemannian Geometry
• Triangulating a simple polygon in linear time
• Special cube complexes
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• Computing Medians and Means in Hadamard Spaces
• Two algorithms for constructing a Delaunay triangulation
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Touring a sequence of polygons
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Computing Geodesic Distances in Tree Space
• Euclidean shortest paths in the presence of rectilinear barriers
• The Discrete Geodesic Problem
• Ends of Group Pairs and Non-Positively Curved Cube Complexes
• Optimal shortest path queries in a simple polygon
• The Ultimate Planar Convex Hull Algorithm?
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• Geodesics in CAT(0) cubical complexes
• CAT(0) is an algorithmic property
• The geometry and topology of reconfiguration
• Median graphs, parallelism and posets
• Relative convex hulls in semi-dynamic arrangements
• Computing minimum length paths of a given homotopy class
• Some results on the geometry of convex hulls in manifolds of pinched negative curvature
• Convexity in Tree Spaces
• Storing the subdivision of a polyhedral surface
• Shortest path problem in rectangular complexes of global nonpositive curvature
• Distance and routing labeling schemes for non-positively curved plane graphs
• Some results on the convex hull of finitely many convex sets
• Limiting behaviour of Fréchet means in the space of phylogenetic trees
• Confidence Sets for Phylogenetic Trees
• Principal component analysis and the locus of the Fréchet mean in the space of phylogenetic trees
• The logarithm map, its limits and Fréchet means in orthant spaces
• Horoball Hulls and Extents in Positive Definite Space
• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes

Cited In (2)

• Convexity in Tree Spaces
• Maximum likelihood estimation of log-concave densities on tree space

Uses Software

• MrBayes

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)