We propose new query applications of the well known randomized incremental construction of the Trapezoidal Search DAG (TSD) on a set of $n$ line segments in the plane, where queries are allowed to be any axis aligned window. We show that our algorithm reports the $m$ trapezoids that are intersected by the query in $\mathcal{O}(m+\log n)$ expected time, regardless of the spatial location of the segment set and the query. In case the query is a {\em vertical segment}, the query time bound reduces to $\mathcal{O}(k +\log n)$ where $k$ is the number of segments that are intersected. This improves on the query and space bound of the well known Segment Tree based approach, which is to date the theoretical bottleneck for optimal query time. In the case where the set of segments is a connected planar subdivision, this method can easily be extended to an algorithm which reports the $k$ segments which intersect an axis aligned query window in $\mathcal{O}(k + \log n)$ expected time. Our publicly available implementation handles degeneracies exactly, including segments with overlap and multi-intersections. Experiments show that the method is practical and provides more reliable query times in comparison to R-trees and the segment tree based data structure on real-world and synthetic data sets.
翻译:我们建议对已知的 Trapexoidal Search DAG (TSD) 进行新的随机递增构建, 在平面上一组 $n 的线段中, 允许查询为任何轴对齐窗口 。 我们显示我们的算法报告以 $\ mathcal{O} (m ⁇ log n) 的查询中, 以 $ 来将已知的 Trapezoid 的随机递增 递增, 不论部分集和查询的空间位置如何 。 如果查询是 $ k$ 的垂直段, 查询时间约束为$\ mathcal{O} (k ⁇ log n) 美元, 其中, $k 美元是交错的段数 。 这在已知的片段树基的查询和空域中, 也就是将理论的瓶颈时间日期与最佳查询时间相交配 。 如果各段是连接的平面平面查询窗口 $\ {R_ log n_log n_log n_log\ creal deal creal