TY - JOUR
T1 - Partitioning point sets in arbitrary dimension
AU - Cole, Richard
N1 - Funding Information:
work was supported
PY - 1987
Y1 - 1987
N2 - We introduce a new type of partition called a parallel planes partition. We prove there exists a parallel planes partition of any set of n points in arbitrary dimension. This partition yields a data structure for the half-space retrieval problem in arbitrary dimension; it has linear size and achieves a sublinear query time. Also, we give efficient algorithms for computing this partition.
AB - We introduce a new type of partition called a parallel planes partition. We prove there exists a parallel planes partition of any set of n points in arbitrary dimension. This partition yields a data structure for the half-space retrieval problem in arbitrary dimension; it has linear size and achieves a sublinear query time. Also, we give efficient algorithms for computing this partition.
UR - http://www.scopus.com/inward/record.url?scp=0022281646&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022281646&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(87)90009-0
DO - 10.1016/0304-3975(87)90009-0
M3 - Article
AN - SCOPUS:0022281646
SN - 0304-3975
VL - 49
SP - 239
EP - 265
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2-3
ER -