DROPS

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

Search Results

Documents authored by Kapoor, Sanjiv

Approximate Euclidean Shortest Paths in Polygonal Domains

Abstract

Cite as

Thanks for your feedback!

Could not send message