DEPARTMENT OF COMPUTER SCIENCE

DOCTORAL DISSERTATION DEFENSE

Candidate: Vasilis Capoyleas

Advisor: Janos Pach and Richard Pollack

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.