Applications of convexity to computational geometry
Vasilis Capoyleas · 1994
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 $\epsilon$-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 decreased, 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.