Partitioning point sets in arbitrary dimension (Q1088420)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Partitioning point sets in arbitrary dimension |
scientific article |
Statements
Partitioning point sets in arbitrary dimension (English)
0 references
1987
0 references
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.
0 references
searching
0 references
parallel planes partition
0 references
data structure for the half-space retrieval problem
0 references
sublinear query time
0 references
efficient algorithms
0 references
