[問題] 計算幾何 - stabbing line
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間11年前 (2013/12/03 22:43)推噓3(3推 0噓 4→)留言7則, 3人參與討論串1/3 (看更多)
我在網路上看到一個問題：
給定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
→
12/04 00:14, , 1F
12/04 00:14, 1F
→
12/04 23:01, , 2F
12/04 23:01, 2F
→
12/04 23:24, , 3F
12/04 23:24, 3F
推
12/05 08:22, , 4F
12/05 08:22, 4F
→
12/05 08:22, , 5F
12/05 08:22, 5F
推
12/05 14:30, , 6F
12/05 14:30, 6F
推
12/06 15:32, , 7F
12/06 15:32, 7F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
