分治算法计算好友点数

Question

分治算法计算好友点数

algorithm

3

我有一个问题需要用分治算法来解决。有一个包含N个点的集合S。如果只有两个点p1和p2在S中，且它们在坐标轴上平行的正方形内，那么我们称p1和p2是朋友点。

现在，我需要使用分治算法计算S中有多少个朋友点。

我思考了很长时间，但无法想到好的方法。所以我需要你的帮助。我的英语不太好，如果你有任何问题，请问我，我会添加说明。谢谢。

- Grap Li

一个给定的点可以是多个其他点的朋友吗？想象一组三个点，分别为p1=(-1, 0)，p2=(0, 0)和p3=(+1, 0)。这个集合只有两个朋友点吗？还是会有两对朋友{p1，p2}和{p2，p3}，因此有三个朋友点？ - Axel Kemper

一个给定的点可以是多个其他点的朋友。 - Grap Li

如果点可以是多个其他点的朋友，则最佳算法是构建Voronoi Diagram。然后，给定的点是相邻Voronoi区域中所有其他点的朋友。一个分治算法在这里被描述。与Voronoi Diagram密切相关的是Delaunay Triangulation。它连接相邻的Voronoi points，因此可以看作是“Friendship Diagram”。 - Axel Kemper

2个回答

0

诀窍在于分割的方式，使得各个部分更小，并可独立处理。我们可以使用类似快速排序的枢轴将点分成两组。但要做到这一点比听起来困难得多，因为如果不正确地执行，这些组可能在特殊情况下不会缩小或不独立。

添加朋友: 需要评估的集合大小分别是1(什么都不需要做)、2(添加一对)和3(添加两对中的2，需要检查)

查找枢轴: 计算x和y的平均值，找到最接近它们的点p

分割：将点分成四组a，b，c和d，如下所示。 a，b是左下角和右上角的分区，c，d是左上角和右下角的分区，只保留更好的一个（如果a.size + b.size <= c.size + d.size，则取a，b）。这应该确保即使在特殊情况下，最大的不可分割集合的大小也为3（我不100%确定，但如果它应该更大，算法仍然保持不变，只需添加更多朋友的基本情况）。所有集合都包括枢轴和其他点，如下所示：集合a：x <= p.x || y < p.y，集合b：x > p.x || y >= p.y，集合c：x < p.x || y >= p.y，以及集合d：x >= p.x || y < p.y。我们应该得到两个集合，两个集合都具有约1/2到3/4的总点数，并且可以独立处理。因此，使用此算法可能会多次检测到一对朋友。

例如：

* * *    * * *    * * .   * * *
* * * => * p * => * * . , . * * bottom-left top-right partition
* * *    * * *    * * *   . * *

* * .    * * .    * * .   . . .
* * . => * p . => * * . , * * . top-left bottom-right partition
* * *    * * *    * . .   * * *

. . .    . . .    . . .   . . .
* * . => * * . => * . . , . * * bottom-left top-right partition
* * *    * p *    * * *   . * .

等等……简化：

a | b    top-left bottom-right partition: 1st set: a, b, c, p; 2nd set: b, c, d, p.
- p -
c | d    bottom-left top-right partition: 1st set: a, c, d, p; 2nd set: a, b, d, p.

这些组是独立的，因为ad和cb中的点不能成为朋友，p将永远挡在中间。左上到右下的分区将点a与d分开，而左下到右上的分区将点b与c分开。

- maraca

对不起，我不理解你所说的除法。你能举个例子吗？ - Grap Li

added an example - maraca

分区 b 和 c 将被计算两次。 - Grap Li

你将会得到两个集合，大约有3/4的点数，所以是的，有些对会被重复检测到，但这都在可接受范围内，而且这些集合是相互独立的，并且它们会变得越来越小。如果你将朋友添加到一个集合中，那么这并不重要，重复项将自动被丢弃。递归地重复这个过程10次，那么集合的大小将只占总点数的百万分之二左右。 - maraca

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Axel Kemper · Accepted Answer

以下是（不一定最优的）伪代码算法，您认为呢？

List<Pair<Point, Point>> findFriends(List<Point> points)
{
    List<Pair<Point, Point>> friends = new List<Pair<Point, Point>>();

    if (points.Count > 1)
    {
        if (points.Count == 2)
        {
           friends.Add(new Pair<Point, Point>(points[0], points[1]);
        }
        else
        {
           int xMedian = getMedianX(points);
           int yMedian = getMedianY(points);
           List<Point> topLeftPoints = selectPoints(points, 0, xMedian-1, yMedian, yMax);
           List<Point> bottomLeftPoints = selectPoints(points, 0, xMedian-1, 0, yMedian-1);
           List<Point> topRightPoints = selectPoints(points, xMedian, xMax, yMedian, yMax);
           List<Point> bottomRightPoints = selectPoints(points, xMedian, xMax, yMedian, yMax);

           friends.Add(findFriends(topLeftPoints));
           friends.Add(findFriends(bottomLeftPoints));
           friends.Add(findFriends(topRightPoints));
           friends.Add(findFriends(bottomRightPoints));      
        }
    }

    return friends;
}