計算幾何設定點算法的

Question

我有以下問題運行時間爲O（nlogn）來設計的算法：

鑑於n個點的集合P，確定的值A> 0，使得剪切變換（x，y）→（x + Ay，y）不會改變x座標不等的點的順序（在x方向上）。

即使搞清楚從哪裏開始，我也有很多困難。

任何幫助，將不勝感激！

謝謝！

Answer 1

我認爲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。

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到達按順序排列，並找到所有點對中滿足的最大A'，其中px> qx和py> qy。然後選擇A的值小於A'的值，例如A'/ 2。 （或者，如果問題的目的是找到最大的這樣的A，則只需報告A'值。）

Answer 3

好的，這裏粗略地介紹了一種方法。

按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） - 義）。如果這是一個負值或零（x_（i + 1）（A）< x_i（A）

因此，對於每個dx_i，找到使得dx_i（A）爲零，即 A_i = - （x_（i + 1） - x_i）/（y_（i + 1） - y_i）。您現在有一個係數列表，它會導致在一個連續的這個點不會改變順序，一些A_i將是負的，如果你想要A> 0，則丟棄這些點（負數）。 A_I也會誘發順序互換，所以A> 0的要求是有點任意的。）

找到最小A_I> 0在列表中。因此，任何一個有0 <一個< A_i（min）將是一個不會改變點的順序的剪切。選擇A_i（分鐘），因爲這將帶來兩個點到同一個X，但不會彼此經過。