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

0
下载
关闭预览

相关内容

专知会员服务
80+阅读 · 2021年7月31日
【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
美国化学会 (ACS) 北京代表处招聘
知社学术圈
11+阅读 · 2018年9月4日
carla 体验效果 及代码
CreateAMind
7+阅读 · 2018年2月3日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年11月23日
Arxiv
6+阅读 · 2020年10月8日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
美国化学会 (ACS) 北京代表处招聘
知社学术圈
11+阅读 · 2018年9月4日
carla 体验效果 及代码
CreateAMind
7+阅读 · 2018年2月3日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员