Reachability in a planar subdivision with direction constraints

Daniel Binham, Pedro Machado Manhães De Castro, Antoine Vigneron

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

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 languageEnglish (US)
Title of host publication33rd International Symposium on Computational Geometry, SoCG 2017
EditorsMatthew J. Katz, Boris Aronov
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages171-1715
Number of pages1545
Volume77
ISBN (Electronic)9783959770385
DOIs
StatePublished - Jun 1 2017
Event33rd International Symposium on Computational Geometry, SoCG 2017 - Brisbane, Australia
Duration: Jul 4 2017Jul 7 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume77
ISSN (Print)1868-8969

Conference

Conference33rd International Symposium on Computational Geometry, SoCG 2017
CountryAustralia
CityBrisbane
Period07/4/1707/7/17

Keywords

  • Design and analysis of geometric algorithms
  • Path planning
  • Reachability

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Reachability in a planar subdivision with direction constraints'. Together they form a unique fingerprint.

Cite this