Files in this item
Files  Description  Format 

application/pdf 8127711.pdf (4MB)  (no description provided) 
Description
Title:  Topics in Computational Geometry 
Author(s):  Supowit, Kenneth Jay 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computer Science 
Abstract:  Computational geometry is the branch of complexity theory that deals with geometrical problems, and has received much attention in recent years. Presented here are analyses of algorithms and complexity results for certain geometrical problems. In Chapter 2, we consider the problems of finding a minimum weighted matching and a minimum traveling salesman tour of n points in a unit square in the plane. We present and analyze the performance of certain fast heuristics for these two problems. The performance of a heuristic for the matching (traveling salesman) problem is defined as the worstcase length of the matching (resp. tour) that it produces. Among the results of Chapter 2 is the rather surprising fact that for each of these two problems, there exists an O(n log n) time heuristic whose performance is, neglecting lower order terms, as low as possible. Chapter 3 concerns the computation of the relative neighborhood graph (RNG) of a finite set V of n points in Euclidean space. The RNG, like the minimum spanning tree, is a graph having V as its set of vertices, and has applications for syntactic pattern recognition. The main results of Chapter 3 are: (1) the RNG of n points in the plane can be found in O(n log n) time, which is optimal to within a multiplicative constant. (2) The RNG of the vertices of a convex, nvertex polygon can be found in O(n) time, given the vertices in sorted clockwise order. (3) Under the assumption that no three input points form an isosceles triangle the RNG of n points in ddimensional space can be found in O(n('2)) time for fixed d (GREATERTHEQ) 3. The fastest algorithm previously known for the RNG problem in the plane requires (theta)(n('2)) time, and that for dimensions 3 and higher requires (theta)(n('3)) time. The result (2) implies that also the minimum spanning tree of the vertices of an nvertex convex polygon can be found in O(n) time. In Chapter 4, we consider various geometric covering problems; in particular, problems whose input is a finite set of points in Euclidean space and whose output is a set of balls whose union contains the input points. In Section 4.2 we present and analyze a heuristic technique, which we call the grid heuristic, that can be applied to a wide class of covering problems, among them the Smallest Bomb Problem, the Smallest Enclosing Circle Problem, and the Largest Empty Circle problem. For each of these problems, we show that for each fixed integer d, the grid heuristic for the problem in ddimensional space is very fast and has very good performance, where the performance of a heuristic is defined as the worstcase ratio between the heuristic's solution and the optimal solution. In Section 4.3, we show several point covering problems to beNPhard, including the kPolice Station Problem. In fact, we showthat it is NPhard even to approximate that problem sufficientlyclosely; more precisely, if P (NOT=) NP then there is no polynomial timealgorithm for the kPolice Station Problem whose output is alwayswithin a factor of 2/SQRT.(3(' )(TURNEQ)(' )1.15 of the optimal. 
Issue Date:  1981 
Type:  Text 
Language:  English 
Description:  187 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1981. 
URI:  http://hdl.handle.net/2142/66456 
Other Identifier(s):  (UMI)AAI8127711 
Date Available in IDEALS:  20141213 
Date Deposited:  1981 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois