1 Search Results for "Inkulu, R."

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.11
Approximate Euclidean Shortest Paths in Polygonal Domains

Authors: R. Inkulu and Sanjiv Kapoor

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Given a set P of h pairwise disjoint simple polygonal obstacles in R^2 defined with n vertices, we compute a sketch Omega of P whose size is independent of n, depending only on h and the input parameter epsilon. We utilize Omega to compute a (1+epsilon)-approximate geodesic shortest path between the two given points in O(n + h((lg n) + (lg h)^(1+delta) + (1/epsilon) lg(h/epsilon)))) time. Here, epsilon is a user parameter, and delta is a small positive constant (resulting from the time for triangulating the free space of P using the algorithm in [Bar-Yehuda and Chazelle, 1994]). Moreover, we devise a (2+epsilon)-approximation algorithm to answer two-point Euclidean distance queries for the case of convex polygonal obstacles.
Cite as

R. Inkulu and Sanjiv Kapoor. Approximate Euclidean Shortest Paths in Polygonal Domains. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{inkulu_et_al:LIPIcs.ISAAC.2019.11,
  author =	{Inkulu, R. and Kapoor, Sanjiv},
  title =	{{Approximate Euclidean Shortest Paths in Polygonal Domains}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.11},
  URN =		{urn:nbn:de:0030-drops-115075},
  doi =		{10.4230/LIPIcs.ISAAC.2019.11},
  annote =	{Keywords: Computational Geometry, Geometric Shortest Paths, Approximation Algorithms}
}
  • Refine by Author
  • 1 Inkulu, R.
  • 1 Kapoor, Sanjiv

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Computational Geometry
  • 1 Geometric Shortest Paths

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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