1. 首頁
  2. 問答
  3. 給定一組點，找出這三個點中的任何一個是否共線

給定一組點，找出這三個點中的任何一個是否共線

2010-04-29 14 views
15

找到三個點是否在一組點中共線的最佳算法是n。如果它不是微不足道的，也請解釋它的複雜性。給定一組點，找出這三個點中的任何一個是否共線

由於
巴拉

來源

2010-04-29 Boolean

+1

這是你的作業嗎？ – WhirlWind 2010-04-29 02:00:06

+2

這個問題在課上討論過，我知道O（N^2）算法。我在O（N^2）中找到了相當簡單的算法。我想知道是否有更簡單的算法。 – Boolean 2010-04-29 02:01:22

+0

這2d點？ – 2010-04-29 02:26:31

回答

15

如果你能想出比O（N^2）更好的算法，你可以發佈它！

這個問題是3-SUM Hard，以及是否存在亞二次算法（即比O（N^2）更好），因爲它是一個開放性問題。許多常見的計算幾何問題（包括你的）已被證明是3SUM的難題，這類問題正在增加。像NP硬度一樣，3SUM硬度的概念已被證明可用於證明某些問題的「韌性」。

對於一個證明，你的問題是3SUM難，是指這裏的優秀surver紙：在上述紙3頁（通稱爲3-POINTS-ON-LINE）上顯示http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf

您的問題。

因此，目前最有名的算法是O（N^2），你已經擁有了它:-)

來源

2010-05-07 04:58:18

+0

謝謝@Moron。該鏈接非常有幫助。 – Boolean 2010-05-07 09:23:23

+0

@Moron - 是否有一個算法的時間爲'O（n^2）'這不是使用散列表作爲@Strilanc描述的算法？ – 2010-07-08 06:26:56

+1

@Elazar：我認爲有可能通過考慮雙線映射到點，反之亦然（a，b）<-> y = ax + b。現在這個問題對應於在至少有6度的對偶中找到頂點。顯然這在O（n^2）時間和O（n^2）空間中是可能的。本書：http://books.google.com/books?id=PBRJ-ruwOQcC在第94頁提到了它。 – 2010-07-08 06:51:45

6

一個簡單的O（d * N^2）的時間和空間的算法，其中d是維數，N是點的數目（可能不是最優的）：

  • 圍繞點集創建邊界框（使其足夠大，以便邊界上沒有點）
  • 對於每對點，計算穿過它們的線。
  • 對於每一行，用邊界框計算它的兩個碰撞點。
  • 兩個碰撞點定義了原始線，所以如果有任何匹配線，它們也會產生相同的兩個碰撞點。
  • 使用散列集合來確定是否有任何重複的碰撞點對。
  • 當且僅當有重複時，共有3個共線點。

來源

2010-04-29 02:21:05

+0

你的情況是必要的，但它是足夠的嗎？在（0,0），（0,1），（1,0）和（1,1）處放4個點來定義邊界框。對[（0.5,0.6），（0.5,0.7）]創建一個與（0.5,0）處的框相交的線段，就像線對[（0.4,0.1），（0.3,0.2）]一樣。然而，八點中沒有三點在任何共同線上。 – Eric 2010-04-29 14:45:09

+1

這是一個充分的條件，因爲兩點定義了一條線。你只考慮了碰撞點對中的一個點;另一個會有所不同，所以這一對不匹配。 – 2010-04-29 15:09:41

+1

你是對的。在步驟2中，您可能想要詳細說明兩個碰撞點放在一起以創建「碰撞點對」。否則，讀者可能會像第一步那樣，在步驟3中將（碰撞點）對與步驟2中的一對（原始點）混淆起來。 – Eric 2010-05-01 00:09:16

4

另一個簡單的（甚至是微不足道的）解決方案，它不使用哈希表，運行速度爲O （N log n）的時間，並且使用O（n）的空間：

讓S是點的集合，我們將介紹其中發現S是否包含某些三點共線點的算法。

  1. 對於每個點o在S做：
    1. 傳遞平行的線L到x - 軸通過o。
    2. 將S中的每個點替換爲L以下的每個點，並進行反思。 （例如，如果L是x軸，則(a,-x)對於x>0將在反射後變爲(a,x)）。讓新的設定點是S'
    3. 每個點p在S'的角度，是段po與線L直角。讓我們按其角度對點S'進行排序。
    4. 瀏覽S'中的排序點。如果有兩個連續的點與o共線 - 返回true。
  2. 如果在循環中找不到共線點 - 返回false。

循環運行n次，每次迭代執行nlog n步驟。不難證明，如果一條線上有三個點，他們將被找到，我們將不會找到其他任何東西。

來源

2010-07-08 12:33:13

+0

您只需要對一半的點進行外循環：那些最大的「y」座標值，正確？當你說「有兩個連續點是共線的」時，你的意思是「有兩個連續的點與點o'共線」，我能正確理解你嗎？ – 2011-10-16 00:59:09

+1

第一次觀察是正確的，但它不會改變複雜性。由於對稱性，對於另一半點這樣做是等同的。請注意，您必須先對它們進行排序，這會使算法更加複雜。第二點也是正確的，修復它，謝謝。 – 2011-10-16 07:34:47

相關問題

 相關問題