2022/01/10 by Buchin, Kevin, Custers, Bram, van der Hoog, Ivor +4
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2201.03490
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, O(\mathop\textrmpolylog 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(nm2) space. In case A also contains only points, we present a smaller, O(n + m2 + ε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 nlog nm) query time using only O(nm2 + ε + n2) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.