Diameter, width, closest line pair, and parametric searching Chazelle, Bernard Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 Guibas, Leonidas Sharir, Micha We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε&gt;0, an O(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(8/5+ε) algorithm for computing the width of such a set, and on O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic. Springer 1993 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4045 Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Diameter, width, closest line pair, and parametric searching. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):183-196. doi:<a href="https://doi.org/10.1007/BF02573973">10.1007/BF02573973</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1007/BF02573973 info:eu-repo/semantics/altIdentifier/issn/0179-5376 info:eu-repo/semantics/closedAccess