作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] 面試問到的問題...
時間Thu Dec 13 15:34:05 2012
※ 引述《DJWS (...)》之銘言：
: ※ 引述《Favonia (小西風最乖了*^^*)》之銘言：
: : 總而言之，如果我上個段落後半部沒有想錯的話，先考
: : 慮所有垂直線，然後通過對偶在參數平面上用 Bentley-
: : Ottmann 找交點。全部應該可以在 O(nlgn) 時間內完成。
: Bentley-Ottmann 的時間複雜度其實是 O((n+k)*logn)，其中 k 是交點個數。
: 經過對偶之後，這些直線最多出現 C(n,2) = O(n^2) 個交點。
: 完成的時間最差是 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。
: 考慮兩個直線的交點，也就是兩條直線解聯立方程式。
: 根據公式解，交點的座標範圍一定會在 |a|*|b|+|c|*|d| 之內。
First, I don't understant your notation.
What do you mean by the range |a|*|b|+|c|*|d| ?
It seems not a range in 2D ?
And I have the same question for you.
Assume you have N lines, based on your description
You claim there is a range for the intersection.
Then, how many operations you need to calculate the range?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 142.136.127.136
1F：推 DJWS:(1) 我指的是 Cramer's rule 那些係數 12/13 15:39
2F：→ DJWS:(2) N個頂點對偶成直線, N條直線各自截成N條線段 ---> O(N) 12/13 15:40
3F：→ DJWS:另外我是假設座標都是整數 如果座標-1<0<1那麼範圍就會更大 12/13 15:41
4F：→ DJWS:不過這樣也是可以處理的 先把所有座標放大n倍直到>=1就好了~ 12/13 15:43
5F：→ Leon:Please answer the second question 12/19 12:11