Applications of parametric searching in geometric optimization


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