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

Question

给定一个二维平面,其中有n个点.我需要生成一个划分平面的线的方程,使得一侧有n/2个点,另一侧有n/2个点.(顺便说一句,这不是家庭工作,我只是想解决问题)

Answer 1

我认为这些点是截然不同的,否则甚至可能没有这样的界限.

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

假设点是P1,P2,...,P2n.假设他们并非都在同一条线上.如果是,那么我们可以很容易地形成分裂线.

首先转换点,使所有坐标(x和y)都为正.

现在假设我们在y轴上神奇地具有点Q,使得那些点(即任何无限线Pi-Pj)形成的线不经过Q.

现在由于Q不在点的凸包内,我们可以很容易地看到我们可以通过穿过Q的旋转线来对点进行排序.对于某个旋转角度,一半点将位于一侧而另一半位于另一侧.将位于此旋转线的另一侧,或者换句话说,如果我们考虑按线Pi-Q的斜率对点进行排序,我们可以选择(中位数)th和(中位数+ 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)时间内运行.

Answer 2

1. 在该平面中创建任意线.将每个点投射到该线上,也就是每个点,将该线上的最近点到达该点.

2. 沿任一方向沿线排序这些点,并在该线上选择一个点,使得在任一方向上的线上都有相同数量的点.

3. 获取垂直于穿过该点的第一条线的线.这条线的两边都有原点的一半.

在执行此操作时有一些情况需要避免.最重要的是,如果所有点都在一条线上,则不要选择穿过它的垂直线.事实上,选择那条线本身就不必担心投射点了.就这背后的实际数学而言,矢量预测将非常有用.

Answer 3

这是将点平面划分为两个相等的一半的修改，允许有重叠点的情况（在这种情况下，它会说明答案是否存在）。

If number of points is odd, return "impossible".

Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
    (i.e. we pretend this line is our new X'-axis, and write down the
     X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
    (`O(N)` or faster-if-desired operation)
    (returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians

In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).

这O(N)与其他提议的解决方案不同。

假设存在解决方案，上述方法可能会终止，尽管我没有证据。

除非您检测到重叠点，否则请尝试几次上述算法。如果您检测到大量重叠点，您可能会遇到困难，但有一个非常低效的蛮力解决方案，它涉及检查所有可能的角度：

For every "critical slope range", perform the above algorithm 
  by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.

临界角被定义为可能改变结果的角度（想象对先前答案的解决方案，旋转整个点集，直到一个或多个点与一个或多个其他点交换位置，越过分界线。有其中只有有限多个，我认为它们受点数的限制，因此O(N^2)-O(N^2 log(N))如果您有重叠点，您可能正在查看范围内的某些内容，以进行蛮力方法。