论文标题
单位磁盘范围搜索和应用
Unit-Disk Range Searching and Applications
论文作者
论文摘要
鉴于飞机中$ n $点的集合$ p $，我们考虑了计算查询单元磁盘中$ p $的点数的问题（即所有查询磁盘都具有相同的半径）。我们表明，在平面中单纯范围搜索的主要技术可以适应此问题。例如，通过调整Matoušek的结果，我们可以构建$ O（n）$空间的数据结构，以便可以在$ o（\ sqrt {n}）$ time中回答每个查询。我们的技术导致了其他几个经典问题的改进，例如批处理范围搜索，计数/报告相交的单位圆对，距离选择，离散的2中心等。给定给定$ n $单位磁盘和一组$ n $ n $的$ n $点。以前的工作[Katz and Sharir，1997]在$ O（n^{4/3} \ log n）$时间中解决了问题，而我们的新算法则以$ O（n^{4/3}）$时间运行。
Given a set $P$ of $n$ points in the plane, we consider the problem of computing the number of points of $P$ in a query unit disk (i.e., all query disks have the same radius). We show that the main techniques for simplex range searching in the plane can be adapted to this problem. For example, by adapting Matoušek's results, we can build a data structure of $O(n)$ space so that each query can be answered in $O(\sqrt{n})$ time. Our techniques lead to improvements for several other classical problems, such as batched range searching, counting/reporting intersecting pairs of unit circles, distance selection, discrete 2-center, etc. For example, given a set of $n$ unit disks and a set of $n$ points in the plane, the batched range searching problem is to compute for each disk the number of points in it. Previous work [Katz and Sharir, 1997] solved the problem in $O(n^{4/3}\log n)$ time while our new algorithm runs in $O(n^{4/3})$ time.
