[问题] 计算几何 - 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