Diameter, width, closest line pair, and parametric searching
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir · 1992
We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improve 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 closest pair in a set of n lines in space. All these algorithms are deterministic. We also look at the problem of computing the k-th smallest slope formed by the lines joining n points in the plane. In 1989 Cole, Salowe, Steiger, and Szemere´di 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.