2026-07-20T14:44:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7202 2024-03-06T10:39:58Z ddc:004 open_access

Reachability in a Planar Subdivision with Direction Constraints Binham, Daniel Manhaes de Castro, Pedro Machado Vigneron, Antoine Design and analysis of geometric algorithms Path planning Reachability 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 Omega(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Binham and Pedro Machado Manhaes de Castro and Antoine Vigneron 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.17 urn:nbn:de:0030-drops-72022 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.17 eng https://creativecommons.org/licenses/by/3.0/legalcode