ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
From MaRDI portal
Abstract: CAT(0) metric spaces and hyperbolic spaces play an important role in combinatorial and geometric group theory. In this paper, we present efficient algorithms for distance problems in CAT(0) planar complexes. First of all, we present an algorithm for answering single-point distance queries in a CAT(0) planar complex. Namely, we show that for a CAT(0) planar complex K with n vertices, one can construct in O(n^2 log n) time a data structure D of size O(n^2) so that, given a point x in K, the shortest path gamma(x,y) between x and the query point y can be computed in linear time. Our second algorithm computes the convex hull of a finite set of points in a CAT(0) planar complex. This algorithm is based on Toussaint's algorithm for computing the convex hull of a finite set of points in a simple polygon and it constructs the convex hull of a set of k points in O(n^2 log n + nk log k) time, using a data structure of size O(n^2 + k).
Recommendations
- Efficient geodesics and an effective algorithm for distance in the complex of curves
- Approximation algorithms for geometrical distance problems that are not solvable exactly
- scientific article; zbMATH DE number 730000
- Shortest path problem in rectangular complexes of global nonpositive curvature
- scientific article; zbMATH DE number 1240832
- Tightness and computing distances in the curve complex
- Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons
- The proximal point algorithm in geodesic spaces with curvature bounded above
- A fast algorithm for computing the p-curvature
- Geometric algorithms for minimal enclosing disks in strictly convex normed planes
Cites work
- An efficient algorithm for determining the convex hull of a finite planar set
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- Computing minimum length paths of a given homotopy class
- Convex hulls of finite sets of points in two and three dimensions
- Curvature and geometry of tessellating plane graphs
- Distance and routing labeling schemes for non-positively curved plane graphs
- Euclidean shortest paths in the presence of rectilinear barriers
- Geodesics in CAT(0) cubical complexes
- Geodesics in non-positively curved plane tessellations
- Geometry of the space of phylogenetic trees
- Graphs of some CAT(0) complexes
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- On approximating the Riemannian 1-center
- On the identification of the convex hull of a finite set of points in the plane
- Optimal shortest path queries in a simple polygon
- Shortest path problem in rectangular complexes of global nonpositive curvature
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
- Shortest paths in the plane with polygonal obstacles
- Special cube complexes
- The geometry and topology of reconfiguration
- Triangulating a simple polygon in linear time
Cited in
(5)- CAT(0) is an algorithmic property
- Shortest paths and convex hulls in 2D complexes with non-positive curvature
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- Shortest path problem in rectangular complexes of global nonpositive curvature
This page was built for publication: ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931158)
