推 Favonia:啊我記錯複雜度了 orz 12/13 19:12
推 Favonia:理論上的進展是，很多 O(1) hash 都是隨機 hash 12/13 19:17
→ Favonia:如果找線段不是隨機的，那就有個 O(n^2) 不隨機的演算法 12/13 19:17
→ DJWS:想請問一下隨機和不隨機是什麼意思? 12/13 21:45
※ 引述《Favonia (小西風最乖了*^^*)》之銘言：
: 總而言之，如果我上個段落後半部沒有想錯的話，先考
: 慮所有垂直線，然後通過對偶在參數平面上用 Bentley-
: Ottmann 找交點。全部應該可以在 O(nlgn) 時間內完成。
Bentley-Ottmann 的時間複雜度其實是 O((n+k)*lgn)，其中 k 是交點個數。
經過對偶之後，這些直線最多出現 C(n,2) = O(nn) 個交點。
完成的時間最差是 O(nnlgn) 而不是 O(nlgn)。
事實上還有比 Bentley-Ottmann 更好的演算法：
http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf
理論上可以做到 O(nlgn + k)，在本題中也就是 O(nn)。
只是這個演算法不太容易實作，反倒是原po提出的 hashing 還比較務實。
－
接著說明一下直線截成線段的問題。
對偶的時候，點(a,b)對偶成直線y=ax+b。
考慮兩個直線的交點，也就是兩條直線解聯立方程式。
根據公式解(Cramer's rule)，
ax+by=e, cx+dy=f 這兩條直線，
其交點的x座標範圍一定會在 |e|*|d|+|b|*|f| 之內（當abcdef都是整數）。
所以我們只要設立一個足夠大與一個足夠小的x座標，再把x座標代入到直線中求得y座標，
就可以把直線截成線段，同時保留所有直線交點。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.135.22
※ 編輯: DJWS 來自: 36.225.135.22 (12/13 16:04)
※ 編輯: DJWS 來自: 36.225.135.22 (12/13 16:05)
※ 編輯: DJWS 來自: 36.225.135.22 (12/13 16:16)