---
_id: '4083'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
article_type: original
author:
- first_name: F.
  full_name: Yao, F.
  last_name: Yao
- first_name: David
  full_name: Dobkin, David
  last_name: Dobkin
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Michael
  full_name: Paterson, Michael
  last_name: Paterson
citation:
  ama: Yao F, Dobkin D, Edelsbrunner H, Paterson M. Partitioning space for range queries.
    <i>SIAM Journal on Computing</i>. 1989;18(2):371-384. doi:<a href="https://doi.org/10.1137/0218025">10.1137/0218025</a>
  apa: Yao, F., Dobkin, D., Edelsbrunner, H., &#38; Paterson, M. (1989). Partitioning
    space for range queries. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/0218025">https://doi.org/10.1137/0218025</a>
  chicago: Yao, F., David Dobkin, Herbert Edelsbrunner, and Michael Paterson. “Partitioning
    Space for Range Queries.” <i>SIAM Journal on Computing</i>. SIAM, 1989. <a href="https://doi.org/10.1137/0218025">https://doi.org/10.1137/0218025</a>.
  ieee: F. Yao, D. Dobkin, H. Edelsbrunner, and M. Paterson, “Partitioning space for
    range queries,” <i>SIAM Journal on Computing</i>, vol. 18, no. 2. SIAM, pp. 371–384,
    1989.
  ista: Yao F, Dobkin D, Edelsbrunner H, Paterson M. 1989. Partitioning space for
    range queries. SIAM Journal on Computing. 18(2), 371–384.
  mla: Yao, F., et al. “Partitioning Space for Range Queries.” <i>SIAM Journal on
    Computing</i>, vol. 18, no. 2, SIAM, 1989, pp. 371–84, doi:<a href="https://doi.org/10.1137/0218025">10.1137/0218025</a>.
  short: F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson, SIAM Journal on Computing
    18 (1989) 371–384.
date_created: 2018-12-11T12:06:50Z
date_published: 1989-04-01T00:00:00Z
date_updated: 2022-02-11T07:55:48Z
day: '01'
doi: 10.1137/0218025
extern: '1'
fulldoi: https://doi.org/10.1137/0218025
intvolume: '        18'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://epubs.siam.org/doi/10.1137/0218025
month: '04'
oa: 1
oa_version: Published Version
page: 371 - 384
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2040'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Partitioning space for range queries
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 18
year: '1989'
...