POLYTOPE RANGE SEARCHING AND INTEGRAL GEOMETRY.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

A family of lower bounds on the space-time complexity of simplex range searching is established. It is proved that the worst-case query time is OMEGA (n/ ROOT m), for d equals 2, and more generally, OMEGA (n/log n)/ m**1**/**d), for d greater than equivalent to 3; n is the number of points and m is the amount of storage available. These bounds hold with high probability for a random point-set (from a uniform distribution) and thus are valid in the worst case as well as on the average. They still hold if the query remains congruent to a fixed simplex or even a fixed slab.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages1-10
Number of pages10
ISBN (Print)0818608072, 9780818608070
DOIs
StatePublished - 1987

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'POLYTOPE RANGE SEARCHING AND INTEGRAL GEOMETRY.'. Together they form a unique fingerprint.

Cite this