@article{4045,
  abstract     = {We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved 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(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.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {183 -- 196},
  publisher    = {Springer},
  title        = {{Diameter, width, closest line pair, and parametric searching}},
  doi          = {10.1007/BF02573973},
  volume       = {10},
  year         = {1993},
}