Abstract
在這本論文中，我們要探討下面三個有關最少轉折的問題。?最少多邊形區圍問題：給兩個有限點所形成的集合 S_1和S_2，找一個 K邊的凸多邊形，使得S1中的點都落在此凸多邊形中，且 K的值要最少。?轉折線的近似問題：給一個點集合，我們所要做的是找出一個轉折線來適合此點集合。?最少轉折分割問題：給兩個有限點集合，找出一些彼此不相交的凸多邊形去分割此兩個點集合。第一個問題我們提出了一個 O(n㏒n)時間的演算法，而且我們也證明了我們的方法是所有演算法中最好的，對於特殊的事件來說，我們也提出了一個O(n)的演算法。第二個問題是以前人所提出的問題，我們利用推導的方式證明它是不可解的。第三個問題在1991年被提出，他們可以在 O(n^2㏒n)的時間內解決，我們將他們的方法改進為O(n^2)的時間。最少多邊形區圍問題：給兩個有限點所形成的集合 S_1和S_2，找一個 K邊的凸多邊形，使得S1中的點都落在此凸多邊形中，且 K的值要最少。轉折線的近似問題：給一個點集合，我們所要做的是找出一個轉折線來適合此點集合。最少轉折分割問題：給兩個有限點集合，找出一些彼此不相交的凸多邊形去分割此兩個點集合。第一個問題我們提出了一個 O(n㏒n)時間的演算法，而且我們也證明了我們的方法是所有演算法中最好的，對於特殊的事件來說，我們也提出了一個O(n)的演算法。第二個問題是以前人所提出的問題，我們利用推導的方式證明它是不可解的。第三個問題在1991年被提出，他們可以在 O(n^2㏒n)的時間內解決，我們將他們的方法改進為O(n^2)的時間。In this dissertation, we discuss the following three problemsrelated to link distance.? Minimum polygonal circumscriptionproblem: Given two finite points sets S_1 and S_2. A convex k-gon is referred to as a k-circumscriber of S_1 with respect toS_2 if its interior contains S_1 under the condition that thevertices of this k-gon are a subset of points of S_2. In thisproblem, we want to find a k-circumscriber of S_1 with respectto S_2 for smallest integer k if it exists. And we provide an O(n) time algorithm for solving a special case of this problem.?Polygonal approximation problem:Given a set of points S={P_1,P_2,...., P_n} in R^2 with Pi= (xi, yi) and x_1<x_2<....<xn.Our job is to con- struct a polygonal approximation functionfwhich fits S well. We shall use the Chebyshev error functions.? Minimum turns separation problem: Given two points set R andB in the plane, find a set of disjoint convex polygons whosetotal number of vertices is minimum such that all points of Rare in the interior of these convex polygons and all points ofB are outside of it. In the first problem, we propose analgorithm with O(n㏒n) time complexity to solve this problem.This algorithm is optimal because we shall show thatΩ(n㏒n) isa lower bound of this problem. In the second problem, weproposed an O(n^2) time algorithm which improves previous O(n^2㏒n) time bound. In the third problem, we prove that this pro-blem is NP-hard.