A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes

2017/10/26 by Hayashi, Koyo · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1710.09932

Abstract

This paper presents the first polynomial time algorithm to compute geodesics in a CAT(0) cubical complex in general dimension. The algorithm is a simple iterative method to update breakpoints of a path joining two points using Miller, Owen and Provan's algorithm (2015) as a subroutine. Our algorithm is applicable to any CAT(0) space in which geodesics between two close points can be computed, not limited to CAT(0) cubical complexes.

Cited by

• Consistency of Nonparametric Density Estimators in CAT(0) Orthant Space

Related

• Geodesics in CAT(0) Cubical Complexes
• Convex optimization on CAT(0) cubical complexes
• Efficient geodesics and an effective algorithm for distance in the\n complex of curves
• Polynomial-time algorithms for the curve graph
• Computing the Geodesic Centers of a Polygonal Domain