On range searching with semialgebraic sets
© 1992, Springer Verlag. All rights reserved. Let P be a set of n points in ℝd (d a small fixed positive integer), and let T be a collection of subsets of ℝd, each of which is defined by a constant number of bounded degree polynomials. The T-range searching problem is defined as: Preprocess P into a data structure, so that all points of P lying in a given γ ε Γ can be counted (or reported) efficiently. Generalizing the simplex range searching techniques, we construct a data structure for Γ-range searching with nearly linear space and preprocessing time, which can answer a query in time O(n1-1/b+δ), where d ≤ b ≤ 2d - 3 and δ < 0 is an arbitrarily small constant. The actual value of 6 is related to the problem of partitioning arrangements of algebraic surfaces into constant-complexity cells.
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)