33rd International Symposium on Computational Geometry (SoCG 2017); Leibniz International Proceedings in Informatics (LIPIcs) 77, pp. 17:1–17:15
Research account
Reachability in a Planar Subdivision with Direction Constraints
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.
The paper was presented at the Annual ACM Symposium on Computational Geometry 2017 (SoCG’17), and published in the Proceedings of SoCG 2017, here is the link.