algorithm - 在二维空间中搜索最近和最远矩形的最快方法

Question

假设现在在 2D 空间中，我们有一个矩形列表a、b、c，如下图所示：

_______
|___a_|
         _______
         |     |
         |__b__|


  _______
  |___c_|

现在我想做的是对于每个矩形，我想找到最近的矩形和最远的矩形。例如，对于矩形a，它最近的矩形是b而它最远的矩形是c。当然，解决这个问题的一种蛮力方法是为每个矩形计算它到其余矩形的距离。我认为应该有解决这个问题的快速算法。例如，我可以将 2D 空间分成 10×10 个正方形，然后计算矩形在这个空间中的位置。当我计算最近的矩形时，我只搜索相邻正方形中的矩形。还有其他想法吗？谢谢。

编辑：我承认如果我只对获取最近的矩形感兴趣，使用kd-tree是一个很好的解决方案。但在这里，我也想知道最远的矩形。我不确定在这种情况下使用 kd 树是否会有所帮助。

标签： algorithmgeometrycomputational-geometry

Answer 1

暗示：

众所周知，此类邻近问题可以通过最近和最远邻居的 Voronoi 图来解决。

已知这些图对于一组点在时间 O(n log(n)) 内是可构造的。对于最远多边形问题，已知 O(n log³(n)) 解。但是对于轴对齐的矩形，这个界限可以降低，我不会感到惊讶。

在任何情况下，没有什么是微不足道的。