article published yes Bernard Chazelle author Herbert Edelsbrunner author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833 Leonidas Guibas author Micha Sharir author 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. Springer1993 eng 0179-537610.1007/BF02573973 101183 - 196 yes Chazelle, Bernard, et al. “Diameter, Width, Closest Line Pair, and Parametric Searching.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 183–96, doi:<a href="https://doi.org/10.1007/BF02573973">10.1007/BF02573973</a>. B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Diameter, width, closest line pair, and parametric searching,” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 183–196, 1993. Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “Diameter, Width, Closest Line Pair, and Parametric Searching.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993. <a href="https://doi.org/10.1007/BF02573973">https://doi.org/10.1007/BF02573973</a>. Chazelle, B., Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1993). Diameter, width, closest line pair, and parametric searching. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02573973">https://doi.org/10.1007/BF02573973</a> 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> Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1993. Diameter, width, closest line pair, and parametric searching. Discrete &#38; Computational Geometry. 10(1), 183–196. B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 10 (1993) 183–196. 40452018-12-11T12:06:37Z2022-03-28T14:50:42Z