---
res:
bibo_abstract:
- 'It is shown that, given a set S of n points in $R^3 $, one can always find three
planes that form an eight-partition of S, that is, a partition where at most ${n
/ 8}$ points of S lie in each of the eight open regions. This theorem is used
to define a data structure, called an octant tree, for representing any point
set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed
in polynomial time. With this data structure and its refinements, efficient solutions
to various range query problems in two and three dimensions can be obtained, including
(1) half-space queries: find all points of S that lie to one side of any given
plane; (2) polyhedron queries: find all points that lie inside (outside) any given
polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points
that lie inside (outside) any given circle. The retrieval time for all these queries
is $T(n) = O(n^\alpha + m)$, where $\alpha = 0.8988$ (or 0.8471 in case (3)),
and m is the size of the output. This performance is the best currently known
for linear-space data structures that can be deterministically constructed in
polynomial time.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: F.
foaf_name: Yao, F.
foaf_surname: Yao
- foaf_Person:
foaf_givenName: David
foaf_name: Dobkin, David
foaf_surname: Dobkin
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Edelsbrunner, Herbert
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Michael
foaf_name: Paterson, Michael
foaf_surname: Paterson
bibo_doi: 10.1137/0218025
bibo_issue: '2'
bibo_volume: 18
dct_date: 1989^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0097-5397
- http://id.crossref.org/issn/1095-7111
dct_language: eng
dct_publisher: SIAM@
dct_title: Partitioning space for range queries@
...