Geometric k shortest paths

S. Eriksson-Bique, J. Hershberger, V. Polishchuk, B. Speckmann, S. Suri, T. Talvitie, K.A.B. Verbeek, H. Yildiz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
109 Downloads (Pure)

Abstract

We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the jth path, for 1 = j = k, is the shortest path in the free space that is also homotopically distinct from each of the first j – 1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map (k-SPM), in which the homotopy of the kth shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of T(k2h + kn) on the worst-case complexity of this map. We also describe an O((k3h + k2n) log (kn)) time algorithm for constructing the map. In fact, the algorithm constructs the jth map for every j = k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O(m log n + k) time and uses O(m + k) space, where m is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O(k2 m(m + kn) log (kn)) time. We invite the reader to play with our applet demonstrating k-SPMs [10].
Original languageEnglish
Title of host publicationTwenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015)
Place of PublicationPhiladelpia
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages1616-1625
ISBN (Print)978-1-61197-374-7
DOIs
Publication statusPublished - 2015
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) - Westin San Diego Gaslamp Quarter, San Diego, United States
Duration: 4 Jan 20156 Jan 2015
Conference number: 26
http://www.siam.org/meetings/da15/

Conference

Conference26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
Abbreviated titleSODA '15
CountryUnited States
CitySan Diego
Period4/01/156/01/15
OtherEvent co-located with the 17th Workshop on Algorithm Engineering and Experiments (ALENEX '15) and the 12th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '15)
Internet address

Fingerprint Dive into the research topics of 'Geometric k shortest paths'. Together they form a unique fingerprint.

Cite this