Diameter, width, closest line pair, and parametric searching (Q685180): Difference between revisions

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.