高等演算法-計算幾何(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的比較

比較兩個函數的成長速率不像比較兩個數字這麼簡單,因為函數是一條曲線，可能忽高忽低，因而有以下的比較原則

小時候胖不是胖原則：眼光要放遠，我們在乎的是n很大的時候。
方格紙y軸可以均勻縮放原則:

正式的定義

O(f(n)):所有成長速率相等與慢於f(n)的函數所成之集合(<=的概念) 大O
Ω(f(n)):所有成長速率相等與快於f(n)的函數所成之集合(>=的概念) 大OMEGA
θ(f(n)):所有成長速率相等於f(n)的函數所成之集合(=的概念) 大theta
o(f(n)):所有成長速率慢於f(n)的函數所成之集合(<的概念) 小O
ω(f(n)):所有成長速率快於f(n)的函數所成之集合(>的概念) 小omega

其他的定義

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)

點(Points) = 0-flat = 端點(vertex)
線(Lines) = 1-flat = 邊(edge)
面(Planes) = 2-flat
體() = 3-flat
球(Spheres)
向量(Vector)
內積(inner product)
外積(cross product)
凸集合(Convex Set)

計算幾何(Computational Geometry;CG)

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

凸多邊型(Convex hull)
交點問題(Intersection Problem)：包含了物件或線段的交點偵測或避免，大多用在機械人(Robotics)
- 線段的交點(Line Segment Intersection)
- 平面、多邊形與藝廊問題(Planar Graphs,Polygons and Art Galleries)
切線與最短路徑(Triangulation & Shortest Paths)
Range Searching
Point Location
Voronoi Diagrams
Delaunay Triangulation
Arrangements
Combinatorial Geometry
Epsilon Nets and VC Dimension
Some paradoxes of Higher Dimension
Closet Pair Problem
Binary Space Partitions

凸多邊型(Convex Hull;CH)

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

由reduction可知CH與sort問題關係密切
- 在f(n)的時間內可將sort問題簡化為CH的問題，所以sort問題不會比CH更難
何謂input sensitive與output sensitive
寫一個不考慮演算法的O(n^2) 的虛擬碼
CH的各種演算法與sort的關係與其時間複雜度,特性
- Graham scan
- Jarvis march
- Divide & Conqer
- Quick
- Chans's
Chans's algorithm的support線段副程式的虛擬碼
在CH上的GPA為何?
CH上演算法的極限Ω(n㏒n)

線段的交點(Line Segment Intersection)

定義

在平面上給n條線段，求每2條線段的交點
線段僅給予2個端點的座標
n個線段可能有0個到n^2個交點,假設有I個交點
最一般的演算法，就是比較所有的線段是否有交點，時間複雜度為O(n^2)
希望找到一個output sensitive的演算法，理想的時間複雜度為O(n㏒n + I)

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

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

判斷2線段有無相交

給予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線段有相交
給予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線段的交點座標

給予2條線段座標a(1,2) b(3,4) c(2,4) d(4,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
因為我們知道線段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 ....Ⅱ
將第Ⅱ-Ⅰ式求得t=0.75,帶入第Ⅰ式求得s=0.25,將s代入上式求得交點(2.5,3.5)

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

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

Plane Sweep Algorithm

簡介

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

用到的資料結構

掃瞄線狀態(Sweep Line Status):由上而下有順序的存放掃瞄到的線段名稱
- 以平衡二元樹儲存，以目前掃瞄到線段y座標當索引值
- 插入刪除搜尋的時間複雜度為O(㏒n)
- 遇到事件時以其x座標計算所有在sweep line status中的線段y座標
事件佇列(Event Queue):以x座標記錄所有線段的端點，與線段的交點
- 以平衡二元樹儲存，x座標排序為其索引
- 當掃瞄線遇到線段的開始，結束或交點時才會變動其值
- 線段的端點是在一開始就加入的，但線段的交點是動態加入的

演算法步驟

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