Applications of Convexity in Computational Geometry
1:00 p.m., Thursday, September 9, 1993
Anina please fill this out XXXX
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:
$\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.