---
_id: '4045'
abstract:
- lang: eng
  text: 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.
acknowledgement: '*Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352.
  Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas
  Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational
  Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284,
  by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered
  by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation
  for Scientific Research and Development.'
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: 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.
  mla: 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>.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational
    Geometry 10 (1993) 183–196.
date_created: 2018-12-11T12:06:37Z
date_published: 1993-12-01T00:00:00Z
date_updated: 2022-03-28T14:50:42Z
day: '01'
doi: 10.1007/BF02573973
extern: '1'
intvolume: '        10'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02573973
month: '12'
oa_version: None
page: 183 - 196
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2083'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Diameter, width, closest line pair, and parametric searching
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1993'
...