DIAMETER, WIDTH, CLOSEST LINE PAIR, AND PARAMETRIC SEARCHING

Authors
CHAZELLE B EDELSBRUNNER H GUIBAS L SHARIR M
Citation
B. Chazelle et al., DIAMETER, WIDTH, CLOSEST LINE PAIR, AND PARAMETRIC SEARCHING, Discrete & computational geometry, 10(2), 1993, pp. 183-196
Citations number
32
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, Pure","Computer Applications & Cybernetics",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
10
Issue
2
Year of publication
1993
Pages
183 - 196
Database
ISI
SICI code
0179-5376(1993)10:2<183:DWCLPA>2.0.ZU;2-Z
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 epsilon > 0, an O(n1+epsilon) algorith m for computing the diameter of a point set in 3-space, an O(8/5+epsil on) algorithm for computing the width of such a set, and an O(n8/5+eps ilon) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic.