TY - GEN

T1 - New techniques for computing order statistics in euclidean space

T2 - 1st Annual Symposium on Computational Geometry, SCG 1985

AU - Chazelle, Bernard

PY - 1985/6/1

Y1 - 1985/6/1

N2 - Given a finite point-set S in E3, how hard is it to compute the Jtth largest interdistance, or say, the kt h largest slope or kth largest triangular area formed by points of S? We examine the complexity of a general class of problems built from these examples, and present a number of techniques for deriving nontrivial upper bounds. Surprisingly, these bounds often match or come very close to the complexity of the corresponding extremal problems (e.g.computing the largest or smallest interdistance, slope, etc.).

AB - Given a finite point-set S in E3, how hard is it to compute the Jtth largest interdistance, or say, the kt h largest slope or kth largest triangular area formed by points of S? We examine the complexity of a general class of problems built from these examples, and present a number of techniques for deriving nontrivial upper bounds. Surprisingly, these bounds often match or come very close to the complexity of the corresponding extremal problems (e.g.computing the largest or smallest interdistance, slope, etc.).

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

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

U2 - 10.1145/323233.323251

DO - 10.1145/323233.323251

M3 - Conference contribution

AN - SCOPUS:0040838110

T3 - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

SP - 125

EP - 134

BT - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

PB - Association for Computing Machinery, Inc

Y2 - 5 June 1985 through 7 June 1985

ER -