Diameter, width, closest line pair, and parametric searching

Bernard Chazelle; Herbert Edelsbrunner; Leonidas Guibas; Micha Sharir

doi:10.1007/BF02573973

Diameter, width, closest line pair, and parametric searching

Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir

Research output: Contribution to journal › Article › peer-review

55 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 language	English (US)
Pages (from-to)	183-196
Number of pages	14
Journal	Discrete & Computational Geometry
Volume	10
Issue number	1
DOIs	https://doi.org/10.1007/BF02573973
State	Published - Dec 1993
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1007/BF02573973

Cite this

@article{705be9b560d1453db5a380dd51b1dcf4,

title = "Diameter, width, closest line pair, and parametric searching",

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.",

author = "Bernard Chazelle and Herbert Edelsbrunner and Leonidas Guibas and Micha Sharir",

year = "1993",

month = dec,

doi = "10.1007/BF02573973",

language = "English (US)",

volume = "10",

pages = "183--196",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Diameter, width, closest line pair, and parametric searching

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas

AU - Sharir, Micha

PY - 1993/12

Y1 - 1993/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=51249169067&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249169067&partnerID=8YFLogxK

U2 - 10.1007/BF02573973

DO - 10.1007/BF02573973

M3 - Article

AN - SCOPUS:51249169067

SN - 0179-5376

VL - 10

SP - 183

EP - 196

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

Diameter, width, closest line pair, and parametric searching

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this