2013/06/30 by Daniela Maftuleac
Computer Science · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Convex hull #Curvature #Data Management and Algorithms #Discrete mathematics #Geometry #Mathematics #Path (computing) #Planar #Polygon (computer graphics) #Regular polygon #Shortest path problem #Simple polygon #Topological and Geometric Data Analysis #cs.CG
paper · pdf · doi:10.1142/s0218195914500010
openalex publication_date 2014/03/01 · arxiv created 2014/10/08 · arxiv updated 2014/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 [Formula: see text] with n vertices, one can construct in O(n 2 log n) time a data structure [Formula: see text] of size O(n 2 ) so that, given a point [Formula: see text], the shortest path γ(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).