Diameter, width, closest line pair, and parametric searching (Q685180)

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed \(\varepsilon>0\), an \(O(n^{1+\varepsilon})\) algorithm for computing the diameter of a point set in 3-space, an \(O(^{8/5+\varepsilon})\) algorithm for computing the width of such a set, and an \(O(n^{8/5+\varepsilon})\) algorithm for computing the closest pair in a set of \(n\) lines in space. All these algorithms are deterministic.