论文标题
段可见性计数多边形的查询
Segment Visibility Counting Queries in Polygons
论文作者
论文摘要
让$ p $是一个简单的多边形，带有$ n $顶点，让$ a $是$ m $点或$ p $内部的$ m $点或线段。我们开发的数据结构可以有效地计算从查询点或查询段可见的$ a $的对象数量。我们的主要目的是获得快速的$ O（\ Mathop {\ textrm {polylog}} nm $），查询时间，同时使用尽可能少的空间。如果查询是一个点，则使用$ o（nm^2）$ space的简单可见性解决方案实现$ o（\ log nm）$查询时间。如果$ a $也只包含点，我们会提供一个较小的$ o（n + m^{2 + \ varepsilon} \ log n）$ - 空间，基于多边形层次分解的数据结构。在这些结果的基础上，我们解决了查询是线段的情况，而$ a $仅包含点。这里的主要并发症是该段可能与多边形分解的多个区域相交，并且一个点可能会看到多个这样的片段。尽管有这些问题，我们还展示了如何仅使用$ o（nm^{2 + \ varepsilon} + n^2）$ o（\ log n \ log nm）$查询时间。最后，我们表明我们甚至可以处理$ a $中的对象是具有相同范围的段的情况。
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{\textrm{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^2)$ space. In case $A$ also contains only points, we present a smaller, $O(n + m^{2 + \varepsilon}\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 + \varepsilon} + n^2)$ space. Finally, we show that we can even handle the case where the objects in $A$ are segments with the same bounds.
