Files in this item



application/pdf8127711.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Topics in Computational Geometry
Author(s):Supowit, Kenneth Jay
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
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 worst-case 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, n-vertex 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 d-dimensional 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 n-vertex 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 d-dimensional space is very fast and has very good performance, where the performance of a heuristic is defined as the worst-case ratio between the heuristic's solution and the optimal solution.
In Section 4.3, we show several point covering problems to beNP-hard, including the k-Police Station Problem. In fact, we showthat it is NP-hard even to approximate that problem sufficientlyclosely; more precisely, if P (NOT=) NP then there is no polynomial timealgorithm for the k-Police Station Problem whose output is alwayswithin a factor of 2/SQRT.(3(' )(TURNEQ)(' )1.15 of the optimal.
Issue Date:1981
Description:187 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
Other Identifier(s):(UMI)AAI8127711
Date Available in IDEALS:2014-12-13
Date Deposited:1981

This item appears in the following Collection(s)

Item Statistics