Abstract

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 number of objects from \(A\) that are visible to a query point or a query segment. Our main aim is to obtain fast, \(\bO(\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 \(\bO(\log nm)\) query time using \(\bO(nm^2)\) space. In case \(A\) also contains only points, we present a smaller, \(\bO(n + m^{2 + \eps}\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 \(\bO(\log n\log nm)\) query time using only \(\bO(nm^{2 + \eps} + n^2)\) space. Finally, we show that we can even handle the case where the objects in \(A\) are segments with the same bounds.

Corresponding Publications

Segment Visibility Counting Queries in Polygons

Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, Frank Staals

Proc. 33th International Symposium on Algorithms and Computation, 2022

Download Local Copy View Slides Export Citation

@inproceedings{segmentvis2022,
  author = {Buchin, Kevin and Custers, Bram and van der Hoog, Ivor and
                 L{\"o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel
                 and  Staals, Frank},
  title = {Segment Visibility Counting Queries in Polygons},
  booktitle = {Proc. 33th International Symposium on Algorithms and Computation},
  year = {2022},
  keywords = {Visibility, Data Structure, Polygons, Complexity},
  category = {datastructures},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  pages = {58:1--58:16},
  volume = {248},
  editor = {Bae, Sang Won and Park, Heejin},
  doi = {10.4230/LIPIcs.ISAAC.2022.58},
  url = {https://doi.org/10.4230/LIPIcs.ISAAC.2022.58},
}