On range searching with semialgebraic sets
Published
Conference Paper
© 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.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Matoušek, J
Published Date
- January 1, 1992
Published In
Volume / Issue
- 629 LNCS /
Start / End Page
- 1 - 13
Electronic International Standard Serial Number (EISSN)
- 1611-3349
International Standard Serial Number (ISSN)
- 0302-9743
International Standard Book Number 13 (ISBN-13)
- 9783540558088
Digital Object Identifier (DOI)
- 10.1007/3-540-55808-x_1
Citation Source
- Scopus