Abstract
Given a planar subdivision with n vertices, each face having a cone of possible directions of travel, our goal is to decide which vertices of the subdivision can be reached from a given starting point s. We give an O(n log n)-time algorithm for this problem, as well as an Ω(n log n) lower bound in the algebraic computation tree model. We prove that the generalization where two cones of directions per face are allowed is NP-hard.
| Original language | English (US) |
|---|---|
| Title of host publication | 33rd International Symposium on Computational Geometry, SoCG 2017 |
| Editors | Matthew J. Katz, Boris Aronov |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Pages | 171-1715 |
| Number of pages | 1545 |
| ISBN (Electronic) | 9783959770385 |
| DOIs | |
| State | Published - Jun 1 2017 |
| Externally published | Yes |
| Event | 33rd International Symposium on Computational Geometry, SoCG 2017 - Brisbane, Australia Duration: Jul 4 2017 → Jul 7 2017 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 77 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 33rd International Symposium on Computational Geometry, SoCG 2017 |
|---|---|
| Country/Territory | Australia |
| City | Brisbane |
| Period | 07/4/17 → 07/7/17 |
Bibliographical note
Publisher Copyright:© Daniel Binham, Pedro Machado Manhães de Castro, and Antoine Vigneron.
Keywords
- Design and analysis of geometric algorithms
- Path planning
- Reachability
ASJC Scopus subject areas
- Software