作者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