License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.17
URN: urn:nbn:de:0030-drops-72022
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7202/
Go to the corresponding LIPIcs Volume Portal


Binham, Daniel ; Manhaes de Castro, Pedro Machado ; Vigneron, Antoine

Reachability in a Planar Subdivision with Direction Constraints

pdf-format:
LIPIcs-SoCG-2017-17.pdf (0.6 MB)


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 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.

BibTeX - Entry

@InProceedings{binham_et_al:LIPIcs:2017:7202,
  author =	{Daniel Binham and Pedro Machado Manhaes de Castro and Antoine Vigneron},
  title =	{{Reachability in a Planar Subdivision with Direction Constraints}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7202},
  URN =		{urn:nbn:de:0030-drops-72022},
  doi =		{10.4230/LIPIcs.SoCG.2017.17},
  annote =	{Keywords: Design and analysis of geometric algorithms, Path planning, Reachability}
}

Keywords: Design and analysis of geometric algorithms, Path planning, Reachability
Seminar: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 08.06.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI