10
$\begingroup$

I am seeking a good introductory reference that could lead to an understanding of the properties of geodesics in complete CAT(0) metric spaces. I am especially interested in learning the differences between geodesics in these spaces and those in an $n$-dimensional Euclidean space with its usual Euclidean metric, which is of course CAT(0). I am ultimately interested in simplicial, cubical, and polyhedral complexes, but I am willing to start anywhere. Thanks for educating me!

           alt text (source)
           [Image from "Shortest path problem in rectangular complexes of global nonpositive curvature" (Elsevier link)]

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Have you had a look at Bridson-Haefliger? math.psu.edu/petrunin/papers/scans/books/bridson.haefliger.pdf $\endgroup$
    – Ian Agol
    Jul 14, 2012 at 1:26
  • $\begingroup$ Thanks, Ian, that book (Metric Spaces of NonPositive Curvature, 2009) seems perfect, even freely downloadable as PDF (in comparison to 122 $US to purchase new!)---Thanks! $\endgroup$
    – Joseph O'Rourke
    Jul 14, 2012 at 1:48
  • 2
    $\begingroup$ I, too, would like to better understand CAT(0) metric spaces. In addition to the Bridson-Haefliger book, I have had recommended to me "A course in metric geometry", by Burago, Burago, and Ivanov. $\endgroup$
    – Russ Woodroofe
    Jul 14, 2012 at 5:09
  • 2
    $\begingroup$ See also Ballmann's "Lectures on spaces of nonpositive curvature", math.psu.edu/petrunin/papers/akp-papers/ballmann-lect.pdf The advantage over Bridson and Haefliger is that Ballmann's book is shorter and has all the staff that you need. $\endgroup$
    – Misha
    Jul 14, 2012 at 13:55

4 Answers 4

Reset to default
8
$\begingroup$

Your pictures remind me of the space of phylogenetric trees (which is cubical and exhibits similar folding), so if you are interested in reading about very concrete such examples, you might take a look at:

  1. L. Billera, S. Holmes, K. Vogtmann, Geometry of the space of phylogenetic trees, Advances in Applied Math, 27 (2001), no. 4, 733-467.
  2. M. Owen and S. Provan, A fast algorithm for computing geodesic distances in tree space, IEEE/ACM Trans. Computational Biology and Bioinformatics, 8: 2-13, 2011.
  3. F. Ardila, M. Owen and S. Sullivant, Geodesics in CAT(0) Cubical Complexes, Advances in Applied Math. 48 (2012), 142-163.

(1) proves uniqueness of geodesics in tree space, (2) gives a polynomial time algorithm to find geodesic distances, and (3) works in more generality.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great references, Patricia, directly hitting my interests---Thanks! $\endgroup$
    – Joseph O'Rourke
    Jul 14, 2012 at 1:56
2
$\begingroup$

The canonical reference is Bridson and Haefliger, Metric Spaces of non-positive curvature

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah, I didn't read the comments :( $\endgroup$
    – Igor Rivin
    Jul 14, 2012 at 13:11
2
$\begingroup$

A more recent reference for geodesics is the following preprint:

Koyo Hayashi. A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes. Oct 2017, arXiv:1710.09932.

Even though the title says "cubical complexes", from the abstract:

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! Note their algorithm finds an approximation, a path of length at most $d(p,q)+\epsilon$, with the time complexity including $\log (1/\epsilon)$. I do not know if there is a polynomial-time exact algorithm. $\endgroup$
    – Joseph O'Rourke
    Dec 9, 2017 at 17:57
  • $\begingroup$ Thanks for pointing out -- not sure if there exists a good rounding to obtain an / the exact solution. In any case, I'm typically happy with weakly polytime methods, especially those with the "luxury" of $\log(1/\epsilon)$ :-) $\endgroup$
    – Suvrit
    Dec 9, 2017 at 22:21
  • $\begingroup$ Oh, yes, I don't mean to diminish Hayashi's achievement. But the holy grail is an exact, polynomial-time algorithm. $\endgroup$
    – Joseph O'Rourke
    Dec 10, 2017 at 0:08
2
$\begingroup$

You may try our book An invitation to Alexandrov geometry: CAT(0) spaces. It contains a chapter about cubical complexes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.