TY - JOUR

T1 - Partitioning space for range queries

AU - Yao, F. Frances

AU - Dobkin, David P.

AU - Edelsbrunner, Herbert

AU - Paterson, Michael S.

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1989

Y1 - 1989

N2 - It is shown that, given a set S of n points in R3, 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 R3. 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 R2: 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(nalpha + m), where α = 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.

AB - It is shown that, given a set S of n points in R3, 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 R3. 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 R2: 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(nalpha + m), where α = 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.

UR - http://www.scopus.com/inward/record.url?scp=0024647064&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024647064&partnerID=8YFLogxK

U2 - 10.1137/0218025

DO - 10.1137/0218025

M3 - Article

AN - SCOPUS:0024647064

VL - 18

SP - 371

EP - 384

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 2

ER -