DEPARTMENT OF COMPUTER SCIENCE
DOCTORAL DISSERTATION DEFENSE

Candidate: Vasilis Capoyleas
Advisor: Janos Pach and Richard Pollack

Applications of Convexity in Computational Geometry

1:00 p.m., Thursday, September 9, 1993
Anina please fill this out XXXX

Abstract

We present seven results in computational geometry. The concept of convexity plays a vital role in all seven of the results; either as a tool in the proof method or as a means of giving a formal definition.

The topics considered are:

Weak $\epsilon$-nets: We provide strong upper bounds for the size of the smallest weak [IMAGE ]-net of a set of points, in two basic cases.

Geometric Clusterings: We provide the first polynomial algorithm to find an optimal clustering of a set of points in the plane. The optimality criteria are based on the diameter and radius of the clusters.

The Hadwiger-Kneser-Thue Poulsen conjecture: This famous 40 year old conjecture states that the area of the union of a set of disks is diminished if the disks are pushed together. We provide two partial results to this conjecture.

Grasping: We consider grasping of polygonal objects by a pair of parallel jaws. We define a model and prove that a fairly large class of polygons can be grasped under this model.

Graph drawing and crossing numbers: We consider the problem of estimating the maximum number of edges for graphs that satisfy some sort of a relaxed planarity condition. We provide exact bounds for an important special case.