algorithm - 到矩形缓存的最短距离

Question

我有一个不必与轴平行的矩形列表。我还有一个与轴平行的主矩形。
我需要一种算法来判断哪个矩形是最接近的点(该点必须在主矩形中)。矩形列表和主矩形在算法过程中不会改变，并且会用很多点调用，因此应该创建一些数据结构来加快查找速度。
明确一点:矩形到点的距离是矩形中最近的点到该点的距离。
什么算法/数据结构可以用于此？内存在这方面具有更高的优先级，n log n 可以，但 n^2 不行。

Answer 1

您应该能够使用 O(n log n) 预处理时间和 O(log n) 时间查询的 Voronoi 图来执行此操作。因为对象是矩形而不是点，所以单元格可能是弯曲的。尽管如此，Voronoi 图应该可以很好地满足您的目的。 (参见 http://en.wikipedia.org/wiki/Voronoi_diagram)

对于您实际上可以在一天内开始工作的快速而肮脏的解决方案，您可以做一些受局部敏感散列启发的事情。例如，如果矩形之间的间距比较合适，您可以将它们散列到具有几个不同偏移量的方形桶中，然后对于每个查询，检查落在包含查询点的少数几个桶之一中的每个矩形。