Diameter, width, closest line pair, and parametric searching

Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir

Research output: Contribution to journalArticle

52 Scopus citations

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(n 1+ε) 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(n 8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic.

Original languageEnglish (US)
Pages (from-to)183-196
Number of pages14
JournalDiscrete & Computational Geometry
Volume10
Issue number1
DOIs
StatePublished - Dec 1 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Diameter, width, closest line pair, and parametric searching'. Together they form a unique fingerprint.

Cite this