TY - GEN

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

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas

AU - Sharir, Micha

PY - 1992/1/1

Y1 - 1992/1/1

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(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(n8/5+ε) algorithm for computing the width of such a set, and an O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic. We also look at the problem of computing the κ-th smallest slope formed by the lines joining n points in the plane. In 1989 Cole, Salowe, Steiger, and Szemeredi gave an optimal but very complicated O(n log n) solution based on Megiddo's technique. We follow a different route and give a very simple O(n log2 n) solution which bypasses parametric searching altogether.

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(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(n8/5+ε) algorithm for computing the width of such a set, and an O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic. We also look at the problem of computing the κ-th smallest slope formed by the lines joining n points in the plane. In 1989 Cole, Salowe, Steiger, and Szemeredi gave an optimal but very complicated O(n log n) solution based on Megiddo's technique. We follow a different route and give a very simple O(n log2 n) solution which bypasses parametric searching altogether.

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

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

U2 - 10.1145/142675.142702

DO - 10.1145/142675.142702

M3 - Conference contribution

AN - SCOPUS:0026990172

SN - 0897915178

SN - 9780897915175

T3 - Eighth Annual Symposium On Computational Geometry

SP - 120

EP - 129

BT - Eighth Annual Symposium On Computational Geometry

PB - Publ by ACM

T2 - Eighth Annual Symposium On Computational Geometry

Y2 - 10 June 1992 through 12 June 1992

ER -