Partitioning point sets in arbitrary dimension

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)239-265
Number of pages27
JournalTheoretical Computer Science
Issue number2-3
StatePublished - 1987

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Partitioning point sets in arbitrary dimension'. Together they form a unique fingerprint.

Cite this