计算几何点集算法
我必须为以下问题设计一个运行时间为 O(nlogn) 的算法：
给定 n 个点的集合 P，确定值 A > 0 使得剪切变换 (x,y) -> 0 (x+Ay,y) 不会更改 x 坐标不相等的点的顺序（x 方向）。
我什至不知道从哪里开始。
任何对此的帮助将不胜感激！
谢谢你！
I have to design an algorithm with running time O(nlogn) for the following problem:
Given a set P of n points, determine a value A > 0 such that the shear transformation (x,y) -> (x+Ay,y) does not change the order (in x direction) of points with unequal x-coordinates.
I am having a lot of difficulty even figuring out where to begin.
Any help with this would be greatly appreciated!
Thank you!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为 y = 0。x
坐标不相等，(2,0)、(3,0)、(4,0)...
所以，我认为起始点可能是(0,0)，x=0。
I think y = 0.
with unequal x-coordinates, (2,0), (3,0), (4,0)...
So, I think that the begin point may be (0,0), x=0.
假设所有 x,y 坐标均为正数。 （不失一般性，可以添加偏移量。）在时间 O(n log n) 内，对点列表 L 进行排序，首先按 x 坐标升序，其次按 y 坐标升序。在时间 O(n) 内，按如下方式处理点对（按 L 顺序）。设p、q为L中任意两个连续点，并令px、qx、py、qy表示它们的x和y坐标值。从这里开始，您只需要考虑几种情况，应该做什么就很明显了：如果 px=qx，则不执行任何操作。否则，如果 py<=qy，则不执行任何操作。否则 (px>qx, py>qy) 要求 px + A*py < qx + A*qy，即 (px-qx)/(py-qy) > A.
所以：按顺序遍历L，找到所有px>qx且py>qy的点对都满足的最大A'。然后选择一个比A'稍小的A值，例如A'/2。 （或者，如果问题的目标是找到最大的 A，则只需报告 A' 值。）
Suppose all x,y coordinates are positive numbers. (Without loss of generality, one can add offsets.) In time O(n log n), sort a list L of the points, primarily in ascending order by x coordinates and secondarily in ascending order by y coordinates. In time O(n), process point pairs (in L order) as follows. Let p, q be any two consecutive points in L, and let px, qx, py, qy denote their x and y coordinate values. From there you just need to consider several cases and it should be obvious what to do: If px=qx, do nothing. Else, if py<=qy, do nothing. Else (px>qx, py>qy) require that px + A*py < qx + A*qy, i.e. (px-qx)/(py-qy) > A.
So: Go through L in order, and find the largest A' that is satisfied for all point pairs where px>qx and py>qy. Then choose a value of A that's a little less than A', for example, A'/2. (Or, if the object of the problem is to find the largest such A, just report the A' value.)
好的，这是一个粗略的方法。
按 x 顺序对点列表进行排序。 （这给出了 O(nlogn) - 以下所有步骤都是 O(n)。）
生成 dx_i = x_(i+1) - x_i 的新列表，即 x 坐标之间的差异。由于 x_i 是有序的，因此所有这些 dx_i >= 0。
现在对于某些 A，变换后的 dx_i(A) 将是 x_(i+1) -x_i + A * ( y_(i+1) - y_i)。如果为负或零 (x_(i+1)(A) < x_i(A)，则会发生顺序变化。
因此，对于每个 dx_i，找到使 dx_i(A) 为零的 A 值，即
A_i = - (x_(i+1) - x_i)/(y_(i+1) - y_i)。您现在拥有一个系数列表，这些系数列表将“导致”连续（按 x 顺序）点对之间的顺序交换。注意被零除的情况，但在两个点具有相同 y 的情况下，这些点不会改变顺序。有些 A_i 将为负数，丢弃它们，因为您希望 A>0。 （负A_i也会引起顺序交换，因此A>0的要求有点武断。）
找到最小的A_i>0。列表中有 0 个。所以任意 A 0 < A＜ A_i(min) 将是一个不会改变点顺序的剪切。选择 A_i(min)，因为这将使两个点达到相同的 x，但不会相互交叉。
Ok, here's a rough stab at a method.
Sort the list of points by x order. (This gives the O(nlogn)--all the following steps are O(n).)
Generate a new list of dx_i = x_(i+1) - x_i, the differences between the x coordinates. As the x_i are ordered, all of these dx_i >= 0.
Now for some A, the transformed dx_i(A) will be x_(i+1) -x_i + A * ( y_(i+1) - y_i). There will be an order change if this is negative or zero (x_(i+1)(A) < x_i(A).
So for each dx_i, find the value of A that would make dx_i(A) zero, namely
A_i = - (x_(i+1) - x_i)/(y_(i+1) - y_i). You now have a list of coefficients that would 'cause' an order swap between a consecutive (in x-order) pair of points. Watch for division by zero, but that's the case where two points have the same y, these points will not change order. Some of the A_i will be negative, discard these as you want A>0. (Negative A_i will also induce an order swap, so the A>0 requirement is a little arbitrary.)
Find the smallest A_i > 0 in the list. So any A with 0 < A < A_i(min) will be a shear that does not change the order of your points. Pick A_i(min) as that will bring two points to the same x, but not past each other.