[問題] 計算幾何 - stabbing line

作者: FRAXIS (喔喔)   2013-12-03 22:43:52
我在網路上看到一個問題:
給定n條垂直的線段,設計一個線性的演算法找出是否存在一條直線,
使得此直線與此n條線段都相交。
我的解法是基於二維線性規劃,感覺是比較不直接的方法。
有沒有比較直接的方法呢?
原文如下:
You are given a set of n vertical line segments in the plane.
Present an O(n) efficient algorithm to determine whether
there exists a line that intersects all of these segments.
作者: esrever   2013-02-04 00:14:00
divide & conquer ?
作者: seanwu (海恩)   2013-02-04 23:01:00
二維線性規劃是expected O(n)嗎?啊啊沒事,找到worst case O(n)的做法了
作者: DJWS (...)   2013-02-05 08:22:00
想請叫一下樓上 worst case O(n) 的做法是什麼?教
作者: seanwu (海恩)   2013-02-05 14:30:00
http://goo.gl/DhKcIn 這篇2.1有提到,不過我沒細看XD
作者: DJWS (...)   2013-02-06 15:32:00
多謝!

Links booklink

Contact Us: admin [ a t ] ucptt.com