2026-08-17T16:26:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17343 2024-03-06T10:59:30Z ddc:004 open_access

Segment Visibility Counting Queries in Polygons Buchin, Kevin Custers, Bram van der Hoog, Ivor Löffler, Maarten Popov, Aleksandr Roeloffzen, Marcel Staals, Frank Visibility Data Structure Polygons Complexity Let P be a simple polygon with n vertices, and let A be a set of m points or line segments inside P. We develop data structures that can efficiently count the objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(polylog nm), query times, while using as little space as possible. In case the query is a single point, a simple visibility-polygon-based solution achieves O(log nm) query time using O(nm²) space. In case A also contains only points, we present a smaller, O(n + m^{2+ε} log n)-space, data structure based on a hierarchical decomposition of the polygon. Building on these results, we tackle the case where the query is a line segment and A contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve O(log n log nm) query time using only O(nm^{2+ε} + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Bram Custers and Ivor van der Hoog and Maarten Löffler and Aleksandr Popov and Marcel Roeloffzen and Frank Staals 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.58 urn:nbn:de:0030-drops-173431 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.58 eng https://creativecommons.org/licenses/by/4.0/legalcode