PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 面試問到的問題...

看板Prob_Solve (計算數學 Problem Solving)作者Favonia (小西風最乖了*^^*)時間12年前 (2012/12/13 00:44)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/8 (看更多)

用射影幾何的對偶變換，原本問題「給定一堆點求一條穿過最多點的線」的對偶問題是知名問題「給定一堆線求一個穿過最多線的點」唯一要注意的地方是射影平面在我們一般熟知的平面上加上許多無窮遠「理想點」，每一組平行線都會相交於某個無窮遠的「理想點」。這些理想點又形成一條「理想線」。這些多加的元素讓線跟點完全對稱。撇開這些抽象概念，其中一個對應就是把一個點 (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)