Document Open Access Logo

A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes

Author Koyo Hayashi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.78.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Author Details

Koyo Hayashi
  • Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8656, Japan

Funding

The work was supported by JSPS KAKENHI Grant Number 17K00029, and by JST ERATO Grant Number JPMJER1201, Japan.

Cite As Get BibTex

Koyo Hayashi. A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.78

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 (Adv. in Appl. Math, 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Geodesic
  • CAT(0) Space
  • Cubical Complex

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Aaron Abrams and Robert Ghrist. State complexes for metamorphic robots. The International Journal of Robotics Research, 23:811-826, 2004. Google Scholar
  2. Federico Ardila, Megan Owen, and Seth Sullivant. Geodesics in CAT(0) cubical complexes. Adv. in Appl. Math., 48:142-163, 2012. Google Scholar
  3. Hans-Jürgen Bandelt and Victor Chepoi. Metric graph theory and geometry: a survey. In Jacob E. Goodman, János Pach, and Richard Pollack, editors, Surveys on discrete and computational geometry, volume 453 of Contemp. Math., pages 49-86. Amer. Math. Soc., Providence, RI, 2008. Google Scholar
  4. Jean-Pierre Barthélemy and Julien Constantin. Median graphs, parallelism and posets. Discrete Math., 111:49-63, 1993. Google Scholar
  5. Miroslav Bačák. Convex analysis and optimization in Hadamard spaces. De Gruyter, Berlin, 2014. Google Scholar
  6. Louis J. Billera, Susan P. Holmes, and Karen Vogtmann. Geometry of the space of phylogenetic trees. Adv. in Appl. Math., 27:733-767, 2001. Google Scholar
  7. Martin R. Bridson and André Haefliger. Metric spaces of non-positive curvature. Springer-Verlag, Berlin, 1999. Google Scholar
  8. John Canny and John Reif. New lower bound techniques for robot motion planning problems. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 49-60, 1987. Google Scholar
  9. Victor Chepoi. Graphs of some CAT(0) complexes. Adv. in Appl. Math., 24:125-179, 2000. Google Scholar
  10. Victor Chepoi and Daniela Maftuleac. Shortest path problem in rectangular complexes of global nonpositive curvature. Comput. Geom., 46:51-64, 2013. Google Scholar
  11. S. M. Gersten and H. Short. Small cancellation theory and automatic groups. II. Invent. Math., 105:641-662, 1991. Google Scholar
  12. R. Ghrist and V. Peterson. The geometry and topology of reconfiguration. Adv. in Appl. Math., 38:302-323, 2007. Google Scholar
  13. Robert Ghrist and Steven M. LaValle. Nonpositive curvature and Pareto optimal coordination of robots. SIAM J. Control Optim., 45:1697-1713, 2006. Google Scholar
  14. M. Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. Google Scholar
  15. Ezra Miller, Megan Owen, and J. Scott Provan. Polyhedral computational geometry for averaging metric phylogenetic trees. Adv. in Appl. Math., 68:51-91, 2015. Google Scholar
  16. Joseph S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of computational geometry, pages 633-701. North-Holland, Amsterdam, 2000. Google Scholar
  17. Joseph S. B. Mitchell and Micha Sharir. New results on shortest paths in three dimensions. In Proceedings of the 20th Annual Symposium on Computational Geometry, pages 124-133, 2004. Google Scholar
  18. Mogens Nielsen, Gordon Plotkin, and Glynn Winskel. Petri nets, event structures and domains. I. Theoret. Comput. Sci., 13:85-108, 1981. Google Scholar
  19. Megan Owen. Computing geodesic distances in tree space. SIAM J. Discrete Math., 25:1506-1529, 2011. Google Scholar
  20. Megan Owen and J. Scott Provan. A fast algorithm for computing geodesic distances in tree space. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8:2-13, 2011. Google Scholar
  21. Valentin Polishchuk and Joseph S. B. Mitchell. Touring convex bodies - A conic programming solution. In Proceedings of the 17th Canadian Conference on Computational Geometry, pages 101-104, 2005. Google Scholar
  22. Martin Roller. Poc sets, median algebras and group actions. preprint, University of Southampton, 1998. Google Scholar
  23. Michah Sageev. Ends of group pairs and non-positively curved cube complexes. Proc. London Math. Soc., 71:585-617, 1995. Google Scholar
  24. Micha Sharir. On shortest paths amidst convex polyhedra. SIAM J. Comput., 16:561-572, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact