2026-07-23T08:46:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11507 2024-03-06T10:48:11Z ddc:004 open_access

Approximate Euclidean Shortest Paths in Polygonal Domains Inkulu, R. Kapoor, Sanjiv Computational Geometry Geometric Shortest Paths Approximation Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik R. Inkulu and Sanjiv Kapoor 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.11 urn:nbn:de:0030-drops-115075 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.11 eng https://creativecommons.org/licenses/by/3.0/legalcode