1 Search Results for "Manhaes de Castro, Pedro Machado"

Document
DOI: 10.4230/LIPIcs.SoCG.2017.17
Reachability in a Planar Subdivision with Direction Constraints

Authors: Daniel Binham, Pedro Machado Manhaes de Castro, and Antoine Vigneron

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

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

Daniel Binham, Pedro Machado Manhaes de Castro, and Antoine Vigneron. Reachability in a Planar Subdivision with Direction Constraints. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{binham_et_al:LIPIcs.SoCG.2017.17,
  author =	{Binham, Daniel and Manhaes de Castro, Pedro Machado and Vigneron, Antoine},
  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 =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.17},
  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}
}
  • Refine by Author
  • 1 Binham, Daniel
  • 1 Manhaes de Castro, Pedro Machado
  • 1 Vigneron, Antoine

  • Refine by Classification

  • Refine by Keyword
  • 1 Design and analysis of geometric algorithms
  • 1 Path planning
  • 1 Reachability

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact