algorithm - 计算几何点集算法

Question

我必须为以下问题设计一个运行时间为 O(nlogn) 的算法：

给定 n 个点的集合 P，确定值 A > 0 使得剪切变换 (x,y) -> (x+Ay,y) 不会改变具有不等 x 坐标的点的顺序（在 x 方向上） .

我什至很难弄清楚从哪里开始。

对此的任何帮助将不胜感激！

谢谢！

Answer 1

好的，这是一个粗略的方法。

按 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 < A_i(min) 的 A 都将是一个不会改变点顺序的剪切。选择 A_i(min) 因为这会将两个点带到相同的 x，但不会彼此过去。

Answer 2

假设所有 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' 值。）

Answer 3

我认为 y = 0。

When x = 0, A > 0
(x,y) -> (x+Ay,y)
      -> (0+(A*0),0) = (0,0)
When x = 1, A > 0
(x,y) -> (x+Ay,y)
      -> (1+(A*0),0) = (1,0)

x坐标不等，(2,0), (3,0), (4,0)...所以，我认为起点可能是(0,0)，x=0。