### Abstract

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε > 0, an O(n^{1+ε}) algorithm for computing the diameter of a point set in 3-space, an O(n^{8/5+ε}) algorithm for computing the width of such a set, and an O(n^{8/5+ε}) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic. We also look at the problem of computing the κ-th smallest slope formed by the lines joining n points in the plane. In 1989 Cole, Salowe, Steiger, and Szemeredi gave an optimal but very complicated O(n log n) solution based on Megiddo's technique. We follow a different route and give a very simple O(n log^{2} n) solution which bypasses parametric searching altogether.

Original language | English (US) |
---|---|

Title of host publication | Eighth Annual Symposium On Computational Geometry |

Publisher | Publ by ACM |

Pages | 120-129 |

Number of pages | 10 |

ISBN (Print) | 0897915178, 9780897915175 |

DOIs | |

State | Published - Jan 1 1992 |

Event | Eighth Annual Symposium On Computational Geometry - Berlin, Ger Duration: Jun 10 1992 → Jun 12 1992 |

### Publication series

Name | Eighth Annual Symposium On Computational Geometry |
---|

### Other

Other | Eighth Annual Symposium On Computational Geometry |
---|---|

City | Berlin, Ger |

Period | 6/10/92 → 6/12/92 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)

## Fingerprint Dive into the research topics of 'Diameter, width, closest line pair, and parametric searching'. Together they form a unique fingerprint.

## Cite this

*Eighth Annual Symposium On Computational Geometry*(pp. 120-129). (Eighth Annual Symposium On Computational Geometry). Publ by ACM. https://doi.org/10.1145/142675.142702