Topics in Computational Geometry

Supowit, Kenneth Jay

Permalink

https://hdl.handle.net/2142/66456 Copy

Description

Title

Topics in Computational Geometry

Author(s)

Supowit, Kenneth Jay

Issue Date

1981

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Computer Science

Language

eng

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.

Graduation Semester

1981

Type of Resource

text

Permalink

http://hdl.handle.net/2142/66456

Owning Collections