algorithm - 用于测试使用列表中的任意两个点构建的每个矩形是否包含该列表中的第三个点的快速算法

Question

问题如下:

给定 N (N <= 100,000) 个点的笛卡尔坐标，测试使用其中任意两个构建的每个矩形(面积 > 0)是否至少包含该列表中的另一个点，无论是在矩形内部还是在他的边距上.

我知道 O(N^2) 时间复杂度的算法。我想找到 O(N * logN) 的解决方案。内存不是问题。

当我说两个点定义一个矩形时，我的意思是这两个点位于矩形的两个对角。矩形的边平行于笛卡尔轴。

这里有两个例子:

N = 4

Points:

1 1

3 5

2 4

8 8

不正确:(矩形 (1, 1) - (2, 4) 内部或边缘没有任何点)。

N = 3

Points:

10 9

13 9

10 8

正确。

Answer 1

按照坐标对的max 顺序对点进行排序，从最低到最高 (O(n*log(n)))。从左下点(最低最大坐标)开始，如果顺序中的下一个点不共享原始点的 x 值或其 y 值(例如 (1, 2) 和 (5,2) 共享 2 的 y 坐标，但是 (1,2) 和 (2, 1) 没有共同的坐标)，该点集未通过测试。否则，移动到下一个点。如果以这种方式到达终点 (O(n))，则该集合有效。整个算法是 O(n*log(n))。

说明

共享坐标值的两个点位于平行于其中一个轴的直线上，因此它们之间没有绘制矩形(因为这样的矩形的面积 = 0)。

对于给定的点 p1，如果顺序中的下一个“更大”点 p2 与 p1 直接垂直或水平(即它共享一个坐标值)，然后所有指向 p2 右上角的点与包含 p2 的 p1 形成矩形，所以有集合中没有以 p1 为左下角且缺少内部点的矩形。

但是，如果下一个更大的点是 p2 的对角线，则 p1 <-> p2 矩形没有来自 p2 的点里面的集合，所以集合是无效的。