# Applications of parametric searching in geometric optimization

Published

Conference Paper

We present several applications in computational geometry of Megiddo's parametric searching technique. These applications include: (1) Finding the minimum Hausdorff distance in the Euclidean metric between two polygonal regions under translation; (2) Computing the biggest line segment that can be placed inside a simple polygon; (3) Computing the smallest width annulus that can contain a given set of points in the plane; (4) Solving the 1-segment center problem - given a set of points in the plane, find a placement for a given line segment (under translation and rotation) which minimizes the largest distance from the segment to the given points; (5) Given a set of n points in 3-space, rinding the largest radius r such that if we place a ball of radius r around each point, no segment connecting a pair of points is intersected by a third ball. Besides obtaining efficient solutions to all these problems (which, in every case, either improve considerably previous solutions or are the first non-trivial solutions to these problems), our goal is to demonstrate the versatility of the parametric searching technique.

### Duke Authors

### Cited Authors

- Agarwal, PK; Sharir, M; Toledo, S

### Published Date

- September 1, 1992

### Published In

- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

### Volume / Issue

- Part F129721 /

### Start / End Page

- 72 - 82

### International Standard Book Number 10 (ISBN-10)

- 089791466X

### Citation Source

- Scopus