Diameter, width, closest line pair, and parametric searching

Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

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(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(n8/5+ε) algorithm for computing the width of such a set, and an O(n8/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 log2 n) solution which bypasses parametric searching altogether.

Original languageEnglish (US)
Title of host publicationEighth Annual Symposium On Computational Geometry
PublisherPubl by ACM
Pages120-129
Number of pages10
ISBN (Print)0897915178, 9780897915175
DOIs
StatePublished - Jan 1 1992
EventEighth Annual Symposium On Computational Geometry - Berlin, Ger
Duration: Jun 10 1992Jun 12 1992

Publication series

NameEighth Annual Symposium On Computational Geometry

Other

OtherEighth Annual Symposium On Computational Geometry
CityBerlin, Ger
Period6/10/926/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

    Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1992). Diameter, width, closest line pair, and parametric searching. In 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