TY - GEN
T1 - New techniques for computing order statistics in euclidean space
T2 - 1st Annual Symposium on Computational Geometry, SCG 1985
AU - Chazelle, Bernard
N1 - Publisher Copyright:
© 1985 ACM.
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 -