作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 计算几何 - stabbing line
时间Tue Dec 3 22:43:52 2013
我在网路上看到一个问题：
给定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.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 129.170.195.148
1F：→ esrever:divide & conquer ? 12/04 00:14
2F：→ seanwu:二维线性规划是expected O(n)吗? 12/04 23:01
3F：→ seanwu:啊啊没事，找到worst case O(n)的做法了 12/04 23:24
4F：推 DJWS:想请叫一下楼上 worst case O(n) 的做法是什麽？ 12/05 08:22
5F：→ DJWS: 教 12/05 08:22
7F：推 DJWS:多谢! 12/06 15:32