algorithm - 最近的点到点，最近的点到线

Question

想象一下二维平面中的一组 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     |  

Answer 1

这基本上是对所有候选人的最近邻居搜索。您可以使用 kd tree 加快解决此类问题的速度指数。