Computing homotopic shortest paths efficiently

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k out+k inlogn+n√n), and the randomized algorithm runs in expected time O(k out+k inlogn+n(logn) 1+ε). Here k in is the number of edges in all the paths of Π, and k out is the number of edges in the output paths.

Original languageEnglish (US)
Pages (from-to)162-172
Number of pages11
JournalComputational Geometry: Theory and Applications
Issue number3
StatePublished - Oct 2006


  • Homotopic shortest paths
  • Shortest path in a polygon

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Computing homotopic shortest paths efficiently'. Together they form a unique fingerprint.

Cite this