6

考虑一个包含 n 个二维点的单位正方形。我们说两个点 p 和 q 在一个正方形中是独立的，如果它们之间的欧几里德距离大于 1。一个单位正方形最多可以包含 3 个相互独立的点。我想在 O(n log n) 的给定单位正方形中找到这 3 个相互独立的点。可能吗？请帮我。

这个问题是否可以在 O(n^2) 内解决而不使用任何空间数据结构，如 Quadtree、kd-tree 等？

4

3 回答 3

2

使用四叉树等空间数据结构来存储您的点。四叉树中的每个节点都有一个边界框和一组 4 个子节点，以及一个点列表（叶节点除外）。这些点存储在叶节点中。

点四叉树是对用于表示二维点数据的二叉树的改编。它共享所有四叉树的特征，但它是一棵真正的树，因为细分的中心总是在一个点上。树的形状取决于处理数据的顺序。它通常在比较二维有序数据点时非常有效，通常在O(log n) 时间内运行。

对于每个点，维护一组独立于该点的所有点。

将所有点插入四叉树，然后遍历这些点并使用四叉树找到独立于每个点的点：

main()
{
     for each point p
         insert p into quadtree
         set p's set to empty

     for each point p
         findIndependentPoints(p, root node of quadtree)
}

findIndependentPoints(Point p, QuadTreeNode n)
{
     Point f = farthest corner of bounding box of n
     if distance between f and p < 1
         return  // none of the points in this node or
                 // its children are independent of p

     for each point q in n
         if distance between p and q > 1
             find intersection r of q's set and p's set
             if r is non-empty then
                 p, q, r are the 3 points -> ***SOLVED***
             add p to q's set of independent points
             add q to p's set of independent points

     for each subnode m of n (up 4 of them)
         findIndependentPoints(p, m)
}

您可以加快速度：

find intersection r of q's set and p's set

通过将每个集合存储为四叉树。然后你可以通过在 q 的四叉树中搜索一个独立于 p 的点来找到交点，方法是使用相同的早期输出技术：

// find intersection r of q's set and p's set:
//     r = findMututallyIndependentPoint(p, q's quadtree root)

Point findMututallyIndependentPoint(Point p, QuadTreeNode n)
{
     Point f = farthest corner of bounding box of n
     if distance between f and p < 1
         return  // none of the points in this node or
                 // its children are independent of p

     for each point r in n
         if distance between p and r > 1
             return r

     for each subnode m of n (up 4 of them)
         findMututallyIndependentPoint(p, m)
}

使用四叉树的另一种方法是使用Kd 树，它产生更平衡的树，其中每个叶节点距根的深度相似。在这种情况下，寻找独立点的算法是相同的，只是数据结构中的每个节点最多只能有 2 个而不是 4 个子节点，并且每个级别的边界框的大小都是可变的。

于 2015-04-23T06:19:29.520 回答
1

这是一个错误的解决方案。保留它只是为了评论。如果有人找到基于最小封闭圆的另一种解决方案，请在评论中添加链接。

  1. 解决最小圆问题。

  2. 如果圆的直径 <= 1，则返回 null。

  3. 如果圆由 3 个点确定，则检查哪些是“相互独立的”。如果只有两个，尝试通过迭代找到第三个。

  4. 如果圆由 2 个点确定，则它们是“相互独立的”。尝试通过迭代找到第三个。

最小圆问题可以在 O(N) 中解决，因此整个问题的复杂度也是 O(N)。

于 2015-04-23T09:38:52.690 回答
1

你可能想试试这个。

Pick the top left point (Y) with coordinate (0,1). Calculate distance from each point from the List to point Y.
Sort the result in increasing order into SortedPointList (L)
If the first point (A) and the last point (B) in list L are independent:
    Foreach point P in list L:
        if P is independent to both A and B:
             Return A, B, P
Pick the top right point (X) with coordinate (1,1). Calculate distance from each point from the List to point X.
Sort the result in increasing order into SortedPointList (S)
If the first point (C) and the last point (D) in list L are independent:
    Foreach point O in list S:
        if P is independent to both C and D:
             Return C, D, O
Return null
于 2015-04-23T05:52:12.537 回答