作者Favonia (小西風最乖了*^^*)
站內Prob_Solve
標題Re: [問題] 面試問到的問題...
時間Thu Dec 13 00:44:17 2012
用射影幾何的對偶變換，原本問題
「給定一堆點求一條穿過最多點的線」
的對偶問題是知名問題
「給定一堆線求一個穿過最多線的點」
唯一要注意的地方是射影平面在我們一般熟知的平面上
加上許多無窮遠「理想點」，每一組平行線都會相交於某個
無窮遠的「理想點」。這些理想點又形成一條「理想線」。
這些多加的元素讓線跟點完全對稱。
撇開這些抽象概念，其中一個對應就是把一個點 (a,b)
變成 y = ax + b 這條線。簡單來說，通過一個點的所有可
能的直線的參數，在參數平面上會形成一條直線。
給定一堆線求相交的點，應該可以用 Bentley-Ottmann
演算法，只要小心垂直線和完全平行的線就行了。以下我沒
有仔細想過，有賴大家驗證：參數平面中的垂直線應該是對
應到原來平面中的理想點，大概可以忽略它，因為歐式幾何
裡面沒有理想點。參數平面中的非垂直平行線代表原平面中
相同 a 不同 b 的點... 也就是在原平面中會被垂直線穿過
的點；或用術語來說，這些平行線交於某個理想點，而這個
理想點對應回來就是那條垂直線。
總而言之，如果我上個段落後半部沒有想錯的話，先考
慮所有垂直線，然後通過對偶在參數平面上用 Bentley-
Ottmann 找交點。全部應該可以在 O(nlgn) 時間內完成。
===
我記錯了，Bentley-Ottmann 的複雜度是 O((n+k)lgn)
有其他演算法是 O(nlgn + k). 如果全部要寫成 n 那複雜度
還是 O(n^2).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.39
※ 編輯: Favonia 來自: 140.112.30.39 (12/13 00:46)
※ 編輯: Favonia 來自: 140.112.30.39 (12/13 00:47)
※ 編輯: Favonia 來自: 140.112.30.39 (12/13 19:15)