4

m想象一下二维平面中的一组点，称为“候选点”。然后是以下两种情况之一：

  • 还有一组n点（“对象”） - 见图 1

  • 还有一组n与 X 或 Y 轴共线的线（“对象”） - 参见图 2

我想知道哪个候选对象对具有所有对中最短的笛卡尔距离。

请问，有谁知道这个问题在计算几何中有名称吗？有没有比 O(m*n) 更快的算法？如果对象保持不变，只有候选对象发生变化——通过一些巧妙的预计算，是否有可能比 O(m*n) 更快？

图。1

              c      o
       c
                          o         c      o
           o    c
                             c
              c o              
                       c             o
                                          c
               o                 c
          c

图 2

             |                      c           |  
-------------+----------------------------------+------  
             |                                  |  
             |              c                   |    c  
             c                                  |  
             |                                  |  
-------------+----------------------------------+------  
             |          c            c          |  
-------------+----------------------------------+------  
             |                            c     |
4

4 回答 4

1

这基本上是对所有候选人的最近邻搜索。您可以使用kd 树索引加速这些类型的问题。

于 2013-03-27T22:15:44.140 回答
0

我不明白您将如何从对象创建线条。为每个对象创建两条线：一条垂直线，一条水平线，是吗？

在任何情况下，假设您有垂直线 v1,v2,..,va 和水平线 h1,h2,...,hb。

根据 x 轴偏移量对垂直线进行排序，根据 y 轴偏移量对水平线进行排序。

对候选集中的每个点进行二分搜索以获得最近的垂直和水平线。现在，如何计算最接近的 (candidate,line) 对是微不足道的。

于 2013-03-27T22:04:04.437 回答
0

您要查找的名称很可能是 NNS（请参阅：http ://en.wikipedia.org/wiki/Nearest_neighbor_search ），是的，给定一些时间和空间来对一组静态“对象”进行预计算，它应该可以执行您的搜索速度比 O(n*m) 快。

即使使用构建二叉搜索树的最简单方法，您也应该能够将单个查找的时间复杂度降低到 O(log n)，从而导致整个问题的 O(m log n)。

于 2013-03-27T22:04:23.753 回答
0

你有两个一维问题而不是一个二维问题。在 x 和 y 轴上投影所有“候选对象”，然后将垂直“对象”放置在 x 轴上，水平放置在 y 上。

瞧！两个一维问题。

现在在 1d。

将所有“候选”放入排序数组，对于每个“对象”，使用二进制搜索在该数组中查找包含段（两个最接近的“候选”）。

结果 O(n log m + n log n)

于 2013-04-04T09:37:34.187 回答