On range searching with semialgebraic sets


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