高等演算法-計算幾何(Advanced Algorithm-Computational Geometry)

本網頁以打造無障礙閱讀為目標,可以用任何瀏覽器來觀看本網頁


簡介

Cobham [1964]和Eomond [1965]首先指出,不同的演算法有不同的時間複雜度(time complexity),一些針對well-defined 問題所發展出來的演算法,有些屬於「多項式時間演算法」(polynomial time algorithms),有些則是「指數時間演算法」(exponential time algorithms)。對於後者,當問題的複雜度加大時,會使得該些演算法的演算時間呈指數成長,導致求得解答所需的時間可能需花費數年,甚至數世紀或更長時間。之後,Cook [1971]提出「NP-complete 理論」,從此證實了運用資訊科技演算法求解也存在時間限制。

研讀所需背景

Asymptotic Notations

簡介

假設某個問題是一個函數,而我們想知道,當輸入資料量增加時,這個函數執行的時間會增加多少,簡單的說就是描述某個函數的成長速率是.............也可以說執行時間的長短是資料量多寡的函數某問題的時間複雜度,一般我們以O(big O)來表示。

O的比較

比較兩個函數的成長速率不像比較兩個數字這麼簡單,因為函數是一條曲線,可能忽高忽低,因而有以下的比較原則
  1. 小時候胖不是胖原則:眼光要放遠,我們在乎的是n很大的時候。
  2. 方格紙y軸可以均勻縮放原則:

正式的定義

其他的定義

big o :Ο
通常會是來說明一個演算法的upper bound..
而O(f(n)) 代表此演算法所需花的時間最多為 k * f(n)

omega:Ω
通常會是用來說明一個問題的理論lower bound
而Ω(f(n))代表此問題至少需要時間 k * f(n) 才可以解決

theta:θ
當一個演算法的big O跟它所解決的問題的omega在同一個set裡面時
我們會說它是θ(f(n))
可以說明的是這個演算法很好
跟理論的lower bound完全一樣

但是這些符號不一定是用來表示時間的
也可以拿來描述空間的複雜度
只是初學演算法大部分都是拿時間來做分析而已

函數與數字的比較

θ vs. =
  θ =
transitivity(遞移性) f() a=b ^ b=c ==> a=c
reflexivity(反射性)   a=a
symmetry(對稱性)   a=b ==> b=a
O vs. <=
  O <=
transitivity(遞移性)   a<=b ^ b<=c ==> a<=c
reflexivity(反射性)   a<=a
anti-symmetry(反對稱性)   a<=b ^ b<=a ==> a=b
Ω vs. >=
  Ω >=
transitivity(遞移性)   a>=b ^ b>=c ==> a>=c
reflexivity(反射性)   a>=a
anti-symmetry(反對稱性)   a>=b ^ b>=a ==> a=b
o vs. <
  o <
transitivity(遞移性)   a<b ^ b<c ==> a<c
ω vs. >
  ω >
transitivity(遞移性)   a>b ^ b>c ==> a>c

branch search

幾何觀念(Geometry Concept)

計算幾何(Computational Geometry;CG)

計算幾何要解決的問題經常是肉眼一看就知道答案但解決的方法經常有很多種不同的演算法,且有浮點精確度與退化狀況等問題,一般而言探討的主題有

凸多邊型(Convex Hull;CH)

一般位置假設(General Position Assumption;GPA):3點不共線

線段的交點(Line Segment Intersection)

定義

一般位置假設(General Position Assumption;GPA)

  1. 沒有垂直的線段
  2. 2條線段會交於一點而沒有平行的狀況
  3. 沒有3條線段交於一點的情況

判斷2線段有無相交

  1. 給予2條線段座標a(1,2) b(3,4) c(2,4) d(4,2)
    1. 根據內積公式ax*by-bx*ay, 我們以線段ab為準
    2. |3 4| 與 |3 4| 得出 3*4-2*4=4 與 3*2-4*4=-10
      |2 4|  |4 2|
    3. 一正一負代表2線段有相交
  2. 給予1線段a(1,2) b(3,4),一直線方程式x+y-6=0
    1. 將a座標帶入直線方程式中=>1+2-6<0
    2. 將b座標帶入直線方程式中=>3+4-6>0
    3. 一正一負代表2線段有相交

判斷2線段的交點座標

  1. 給予2條線段座標a(1,2) b(3,4) c(2,4) d(4,2) 經上式計算已知有相交,求交點
  2. 根據convex combination {(x,y)|(x,y)=λ(x1y1)+(1-λ)(x2,y2),for some λ=[0,1]}
    線段ab的公式為s*a + (1-s)*b
    線段cd的公式為t*c + (1-t)*d
  3. 因為我們知道線段ab與線段cd會有交點,所以(s=t)
    x= s*ax + (1-s)*bx = t*cx + (1-t)*dx => s + (1-s)*3 = 2t + (1-t)*4 => 3-2s = 4-2t => 2s-2t=-1 .....Ⅰ
    y= s*ay + (1-s)*by = t*cy + (1-t)*dy => 2s + (1-s)*4 = 4t + (2-2t)*2 => 4-2s = 2+2t => 2s+2t=2 ....Ⅱ
  4. 將第-式求得t=0.75,帶入第式求得s=0.25,將s代入上式求得交點(2.5,3.5)

給2個座標,求直線方程式的公式

  1. 公式為 => (Y-Y1) / (Y2-Y1) = (X-X1) / (X2-X1)
  2. 給予線段座標 (2,4) (4,2)
  3. 代入公式 => (y-4) / (2-4) = (x-2) / (4-2) => -y+4 = x-2
  4. x+y=6

Plane Sweep Algorithm

簡介

翻譯為平面掃瞄演算法:有一條sweep line由左至右掃瞄過去求得所有線段的交點

用到的資料結構

演算法步驟

  1. 將所有的端點資料依x座標排序輸入event queue, sweep line status一開始是空的
  2. 當enent queue不是空的,從queue中取出下一個event
    1. 如果是線段左邊的端點
      1. 將這個線段名稱加入sweep line status,並依y座標排序
      2.  
      與上下2個線段計算有無交點,若有交點則依其x座標加入enent queue
    2. 如果是線段右邊的端點
      1. 從sweep line status刪除其線段名稱
      2. 刪除後的上下線段則再計算有無交點,若有交點則依其x座標加入enent queue
    3. 如果遇到交點
      1. 對調在sweep line status中的線段位置
      2. 重新計算上下2條線段與其鄰近的線段有無交點,若有交點則依其x座標加入enent queue

平面、多邊形與藝廊問題(Planar Graphs,Polygons and Art Galleries)

平面圖(Planar Graph)

一個圖如果可以畫在平面上使得所有的邊都互不跨越(端點除外),即為平面圖。

平面圖(Planar Graph)上的特性:尤拉公式(Euler's formula)

平面線段圖形(Planar Straight line Graph;PSLG)

以直線切割的平面,線段不會相交,通常以DCEL來表示圖形結構

平面切割(Planar Subdivision)

以直線切割的平面,線段會相交,通常以DCEL來表示圖形結構

DCEL(Doubly Connected Edge List)

傳統圖的表示法有相鄰矩陣或相鄰串列,但表示能力不足,DCEL是一種以邊為主的圖形表示法,前提是這個圖中的平面不可以有一個洞

多邊形曲線(Polygonal Curves)

首尾相連自身無相交的多邊形曲線稱之為單純多邊形(Simple Polygons)

simple polygons 若有n個頂點則有n-3個對角線(diagonals),有n-2個三角形(triangles)

藝廊問題(Art Gallery)

將多邊型切割成三角形(Polygon Triangulation)

簡介

Monotone Polygons

半平面的切線(Halfplane Intersection)

線性規劃(Linear Programming)

隨機漸增式演算法(randomized incremental algorithms)

機率分析(probabilistic analysis) = backward analysis

包含所有點的最小圓(Smallest Enclosing Disk)

垂直範圍搜尋(Orthogonal Range Searching)

kd樹( kd-Trees)

網路資源

主 網 站:http://peterju.notlong.com (目前轉址至 http://irw.ncut.edu.tw/peterju/) Sitetag Logo

Level Triple-A conformance icon | [歡迎使用任何作業系統、瀏覽器觀看!] | Valid XHTML 1.0 Transitional | Valid CSS! | [Valid RSS] | [創意公眾許可証]
This work is licensed under a Creative Commons License