2026-07-23T05:04:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5137 2024-03-06T10:35:51Z ddc:004 open_access

Geometric Spanners for Points Inside a Polygonal Domain Abam, Mohammad Ali Adeli, Marjan Homapour, Hamid Asadollahpoor, Pooya Zafar Geometric Spanners Polygonal Domain Visibility Graph Let P be a set of n points inside a polygonal domain D. A polygonal domain with h holes (or obstacles) consists of h disjoint polygonal obstacles surrounded by a simple polygon which itself acts as an obstacle. We first study t-spanners for the set P with respect to the geodesic distance function d where for any two points p and q, d(p,q) is equal to the Euclidean length of the shortest path from p to q that avoids the obstacles interiors. For a case where the polygonal domain is a simple polygon (i.e., h=0), we construct a (sqrt(10)+eps)-spanner that has O(n log^2 n) edges where eps is the a given positive real number. For a case where there are h holes, our construction gives a (5+eps)-spanner with the size of O(sqrt(h) n log^2 n). Moreover, we study t-spanners for the visibility graph of P (VG(P), for short) with respect to a hole-free polygonal domain D. The graph VG(P) is not necessarily a complete graph or even connected. In this case, we propose an algorithm that constructs a (3+eps)-spanner of size almost O(n^{4/3}). In addition, we show that there is a set P of n points such that any (3-eps)-spanner of VG(P) must contain almost n^2 edges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohammad Ali Abam and Marjan Adeli and Hamid Homapour and Pooya Zafar Asadollahpoor 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.186 urn:nbn:de:0030-drops-51378 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.186 eng https://creativecommons.org/licenses/by/3.0/legalcode