将点平面分成两个相等的两半

给定一个二维平面,其中有n个点。我需要生成将平面划分为一条直线的方程,以便一侧有n / 2个点,另一侧有n / 2个点。

回答:

我假设这些点是截然不同的,否则可能根本没有这样一条线。

如果点是不同的,则这样的线将始终存在,并且可以使用 确定性 O(nlogn)时间算法找到。

说点是P1,P2,…,P2n。假设它们不在同一行。如果是这样,那么我们可以轻松地形成分割线。

首先平移点,以使所有坐标(x和y)均为正。

现在假设我们神奇地在y轴上有一个点Q,以使由这些点形成的线(即任何无限线Pi-Pj)都不会穿过Q。

现在,由于Q不在点的凸包内,我们可以很容易地看到,可以通过穿过Q的旋转线对点进行排序。对于某个旋转角度,一半的点将位于一侧,而另一半将位于该旋转线的另一条线上,或者换句话说,如果我们考虑按点Pi-

Q的斜率排序的点,则可以选择第(median)和(median +

1)之间的斜率点。可以通过任何线性时间选择算法在O(n)时间内完成此选择,而无需实际对点进行排序。

现在选择点Q。

假设Q为(0,b)。

假设Q与P1(x1,y1)和P2(x2,y2)共线。

那我们有

(y1-b)/ x1 =(y2-b)/ x2(请注意,我们平移了点,使xi> 0)。

求解b给出

b =(x1y2-y1x2)/(x1-x2)

(请注意,如果x1 = x2,则P1和P2不能与Y轴上的点共线)。

考虑| b |。

| b | = | x1y2-y1x2 | / | x1 -x2 |

现在,让xmax为最右点的x坐标,ymax为最顶点的坐标。

还要使D为两点之间的最小非零x坐标差(存在,因为并非所有x都是相同的,因为并非所有点都是共线的)。

然后有| b | <= xmax * ymax / D。

因此,选择我们的点Q(0,b)为| b | > b_0 = xmax * ymax / D

D可以在O(nlogn)时间找到。

b_0的大小可能会变得很大,我们可能不得不处理精度问题。

当然,更好的选择是随机选择Q!以概率1,您将找到所需的点,从而得出预期的运行时间O(n)。

如果我们可以找到在O(n)时间中选择Q的方法(通过找到其他标准),则可以使该算法在O(n)时间中运行。

以上是 将点平面分成两个相等的两半 的全部内容, 来源链接: utcz.com/qa/403208.html

回到顶部