Volume 22, issue 2 (2022)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 22
Issue 3, 991–1495
Issue 2, 473–990
Issue 1, 1–472

Volume 21, 7 issues

Volume 20, 7 issues

Volume 19, 7 issues

Volume 18, 7 issues

Volume 17, 6 issues

Volume 16, 6 issues

Volume 15, 6 issues

Volume 14, 6 issues

Volume 13, 6 issues

Volume 12, 4 issues

Volume 11, 5 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 4 issues

Volume 7, 4 issues

Volume 6, 5 issues

Volume 5, 4 issues

Volume 4, 2 issues

Volume 3, 2 issues

Volume 2, 2 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editorial Interests
Subscriptions
 
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
 
ISSN (electronic): 1472-2739
ISSN (print): 1472-2747
Author Index
To Appear
 
Other MSP Journals
Two robots moving geodesically on a tree

Donald M Davis, Michael Harrison and David Recio-Mitter

Algebraic & Geometric Topology 22 (2022) 785–814
Abstract

We study the geodesic complexity of the ordered and unordered configuration spaces of graphs in both the 1 and 2 metrics. We determine the geodesic complexity of the ordered two-point 𝜀–configuration space of any star graph in both the 1 and 2 metrics and of the unordered two-point configuration space of any tree in the 1 metric, by finding explicit geodesics from any pair to any other pair, and arranging them into a minimal number of continuously varying families. In each case the geodesic complexity matches the known value of the topological complexity.

Keywords
geodesic, configuration space, topological robotics, graphs
Mathematical Subject Classification
Primary: 53C22, 55M30, 55R80
Secondary: 68T40
References
Publication
Received: 2 July 2020
Revised: 8 December 2020
Accepted: 11 January 2021
Published: 3 August 2022
Authors
Donald M Davis
Department of Mathematics
Lehigh University
Bethlehem, PA
United States
Michael Harrison
Institute for Advanced Study
Princeton, NJ
United States
David Recio-Mitter
Department of Mathematics
Lehigh University
Bethlehem, PA
United States