分割点的平面分成相等的两半 [英] Dividing a plane of points into two equal halves

问题描述

鉴于在其中有n个点的2维平面。我需要生成分割平面，使得有n在另一侧上/ 2点和n / 2个点的直线的方程。 （顺便说一下这个不在家工作，我只是想解决的问题）

Given a 2 dimensional plane in which there are n points. I need to generate the equation of a line that divides the plane such that there are n/2 points on one side and n/2 points on the other. (by the way this not home work, I am just trying to solve the problem)

推荐答案

我假设点是不同的，否则有可能甚至是这样的一条线。

I have assumed the points are distinct, otherwise there might not even be such a line.

如果点是不同的，那么这样的线总是存在，并有可能找到使用的确定的O（nlogn）时间的算法。

If points are distinct, then such a line always exists and is possible to find using a deterministic O(nlogn) time algorithm.

说的点是P1，P2，...，P2N。假定它们是不是所有在同一行上。如果他们成功了，那么我们就可以很容易地形成分割线。

Say the points are P1, P2, ..., P2n. Assume they are not all on the same line. If they were, then we can easily form the splitting line.

首先翻译点，使得所有的坐标（x和y）是正

First translate the points so that all the co-ordinates (x and y) are positive.

现在假设我们神奇地对y轴上的点Q，使得不被那些点（即任何无限线丕PJ）通过Q传递。形成行

Now suppose we magically had a point Q on the y-axis such that no line formed by those points (i.e. any infinite line Pi-Pj) passes through Q.

现在，因为Q未点的凸包之内时，我们可以很容易地看到，我们可以通过旋转一条通过Q：对于旋转一定角度责令点，一半的积分将趴在一边，另一半将躺在另此旋转线，或者，换句话说，如果我们考虑点被分类通过将Pi-Q线的斜率，我们可以挑（中值）和第（中位数之间的斜率+1）个点。这个选择可以在O（n）的时间通过任何线性时间选择算法，而无需任何实际分选点来进行。

Now since Q does not lie within the convex hull of the points, we can easily see that we can order the points by a rotating line passing through Q. For some angle of rotation, half the points will lie on one side and the other half will lie on the other of this rotating line, or, in other words, if we consider the points being sorted by the slope of the line Pi-Q, we could pick a slope between the (median)th and (median+1)th points. This selection can be done in O(n) time by any linear time selection algorithm without any need for actually sorting the points.

现在要挑点Q

说Q值（0，B）。

假设Q值共线P1（X1，Y1）和P2（X2，Y2）。

Suppose Q was collinear with P1 (x1,y1) and P2 (x2,y2).

然后，我们有

（Y1-B）/ X1 =（Y2-b）的/ X2（注意我们翻译点，使得十一> 0）。

(y1-b)/x1 = (y2-b)/x2 (note we translated the points so that xi > 0).

解出B给出

B =（X1Y2 - y1x2）/（X1-X2）

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

（注意，如果，X1 = X2，则P1和P2不能共线在Y轴上的一个点）。

(Note, if x1 = x2, then P1 and P2 cannot be collinear with a point on the Y axis).

考虑| B |

| B | = | X1Y2 - y1x2 | / | X1 -x2 |

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

现在让XMAX是x坐标的最右点和YMAX的坐标的最顶层

Now let the xmax be the x-coordinate of the rightmost point and ymax the co-ordinate of the topmost.

也令D是两个点（这存在，因为不是所有的红双喜都是一样的，因为不是所有的点都共线）。

Also let D be the smallest non-zero x-coordinate difference between two points (this exists, as not all xis are same, as not all points are collinear).

然后，我们有| B | ＆LT; = XMAX * YMAX / D

Then we have that |b| <= xmax*ymax/D.

因此​​，我们挑点Q（0，B）要使得| B | > B_0 = XMAX * YMAX / D

Thus, pick our point Q (0,b) to be such that |b| > b_0 = xmax*ymax/D

D可在O（nlogn）的时间被发现。

D can be found in O(nlogn) time.

B_0的幅度可以得到相当大，我们可能不得不面对precision问题。

The magnitude of b_0 can get quite large and we might have to deal with precision issues.

当然，更好的选择是挑选Q随机！以概率1，你会发现你所需要的点，从而使预期的运行时间为O（n）。

Of course, a better option is to pick Q randomly! With probability 1, you will find the point you need, thus making the expected running time O(n).

如果我们能找到一种方法可以选择在O（n）时间Q（通过寻找一些其他的标准），那么我们可以在O（n）时间算法的运行。

If we could find a way to pick Q in O(n) time (by finding some other criterion), then we can make this algorithm run in O(n) time.

这篇关于分割点的平面分成相等的两半的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！