article
Partitioning space for range queries
published
yes
F.
Yao
author
David
Dobkin
author
Herbert
Edelsbrunner
author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833
Michael
Paterson
author
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.
SIAM1989
eng
SIAM Journal on Computing
0097-5397
1095-711110.1137/0218025
182371 - 384
yes
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>.
Yao F, Dobkin D, Edelsbrunner H, Paterson M. 1989. Partitioning space for range queries. SIAM Journal on Computing. 18(2), 371–384.
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>
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.
F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson, SIAM Journal on Computing 18 (1989) 371–384.
Yao, F., Dobkin, D., Edelsbrunner, H., & 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>
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>.
40832018-12-11T12:06:50Z2022-02-11T07:55:48Z