APPLICATIONS OF PARAMETRIC SEARCHING IN GEOMETRIC OPTIMIZATION

We present several applications in computational geometry of Megiddo's parametric searching technique. These applications include: (1) Findi ng the minimum Hausdorff distance in the Euclidean metric between two polygonal regions under translation; (2) Computing the biggest line se gment that can be placed inside a simple polygon; (3) Computing the sm allest width annulus that contains a given set of given points in the plane; (4) Given a set of n points in 3-space, finding the largest rad ius r such that if we place a ball of radius r around each point, no s egment connecting a pair of points is intersected by a third ball. Bes ides obtaining efficient solutions to all these problems (which, in ev ery case, either improve considerably previous solutions or are the fi rst nontrivial solutions to these problems), our goal is to demonstrat e the versatility of the parametric searching technique. (C) 1994 Acad emic Press, Inc.