@inproceedings{afbe430c2c894d6b8c4aeb7a13c3b873,
title = "Reachability in a planar subdivision with direction constraints",
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.",
keywords = "Design and analysis of geometric algorithms, Path planning, Reachability",
author = "Daniel Binham and {De Castro}, {Pedro Machado Manh{\~a}es} and Antoine Vigneron",
note = "Publisher Copyright: {\textcopyright} Daniel Binham, Pedro Machado Manh{\~a}es de Castro, and Antoine Vigneron.; 33rd International Symposium on Computational Geometry, SoCG 2017 ; Conference date: 04-07-2017 Through 07-07-2017",
year = "2017",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2017.17",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "171--1715",
editor = "Katz, {Matthew J.} and Boris Aronov",
booktitle = "33rd International Symposium on Computational Geometry, SoCG 2017",
address = "Germany",
}