Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Topological complexity of configuration spaces

Authors: Michael Farber and Mark Grant
Journal: Proc. Amer. Math. Soc. 137 (2009), 1841-1847
MSC (2000): Primary 55M99, 55R80; Secondary 68T40
Published electronically: December 29, 2008
MathSciNet review: 2470845
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The topological complexity $ \mathsf{TC}(X)$ is a homotopy invariant which reflects the complexity of the problem of constructing a motion planning algorithm in the space $ X$, viewed as configuration space of a mechanical system. In this paper we complete the computation of the topological complexity of the configuration space of $ n$ distinct points in Euclidean $ m$-space for all $ m\ge 2$ and $ n\ge 2$; the answer was previously known in the cases $ m=2$ and $ m$ odd. We also give several useful general results concerning sharpness of upper bounds for the topological complexity.

References [Enhancements On Off] (What's this?)

  • 1. D. C. Cohen and G. Pruidze, Motion planning in tori, Bull. London Math. Soc. 40 (2008), 249-262. MR 2414784
  • 2. D. C. Cohen and G. Pruidze, Topological complexity of basis-conjugating automorphism groups, preprint. [arXiv:0804.1825]
  • 3. A. Costa and M. Farber, Motion planning in spaces with ``small'' fundamental groups, preprint, 2008.
  • 4. S. Eilenberg and T. Ganea, On the Lusternik-Schnirelmann category of abstract groups, Ann. of Math. (2) 65 (1957), 517-518. MR 0085510 (19:52d)
  • 5. E. R. Fadell and S. Y. Husseini, Geometry and Topology of Configuration Spaces, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2001. MR 1802644 (2002k:55038)
  • 6. M. Farber, Topological complexity of motion planning, Discrete Comput. Geom. 29 (2003), 211-221. MR 1957228 (2004c:68132)
  • 7. M. Farber, Instabilities of robot motion, Topology Appl. 140 (2004), 245-266. MR 2074919 (2005g:68166)
  • 8. M. Farber and S. Yuzvinsky, Topological robotics: Subspace arrangements and collision free motion planning, In ``Geometry, Topology, and Mathematical Physics'', Amer. Math. Soc. Transl. (2) 212, Amer. Math. Soc., Providence, RI, 2004, 145-156. MR 2070052 (2005i:55019)
  • 9. M. Farber, Topology of robot motion planning, in: ``Morse Theoretic Methods in Nonlinear Analysis and in Symplectic Topology'' (P. Biran et al. (eds.)), Springer, Dordrecht, 2006, 185-230. MR 2276952 (2008d:68141)
  • 10. M. Farber and M. Grant, Robot motion planning, weights of cohomology classes, and cohomology operations, Proc. Amer. Math. Soc. 136 (2008), 3339-3349. MR 2407101
  • 11. M. Farber, Invitation to Topological Robotics, EMS, 2008.
  • 12. J. González, Topological robotics in lens spaces, Math. Proc. Cambridge Philos. Soc. 139 (2005), no. 3, 469-485. MR 2177172 (2006f:55006)
  • 13. M. Grant, Topological complexity of motion planning and Massey products, to appear in Proceedings of the M. M. Postnikov Memorial Conference 2007, Banach Centre Publications [arxiv:0709.2287].
  • 14. J.-C. Latombe, Robot Motion Planning, Kluwer, Dordrecht, 1991.
  • 15. A. S. Švarc, The genus of a fiber space, Amer. Math. Soc. Transl. (2) 55, Amer. Math. Soc., Providence, RI, 1966, 49-140.
  • 16. G.W. Whitehead, Elements of Homotopy Theory, Springer-Verlag, New York, 1978. MR 516508 (80b:55001)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 55M99, 55R80, 68T40

Retrieve articles in all journals with MSC (2000): 55M99, 55R80, 68T40

Additional Information

Michael Farber
Affiliation: Department of Mathematical Sciences, Durham University, South Road, Durham, DH1 3LE, United Kingdom

Mark Grant
Affiliation: School of Mathematics, The University of Edinburgh, King’s Buildings, Edinburgh, EH9 3JZ, United Kingdom

Keywords: Topological complexity, configuration spaces
Received by editor(s): June 25, 2008
Published electronically: December 29, 2008
Additional Notes: This research was supported by grants from the EPSRC and from The Royal Society
Communicated by: Alexander N. Dranishnikov
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society