Christian A. Duncan
Michael T. Goodrich
University of California, Irvine
Specializeddata structures are useful for answering specific kinds of geometric queries. Such structures are tailor-made for the kinds of queries that are anticipated and even then there are cases when producing an exact answer is only slightly better than an exhaustive search. For example, Chazelle and Welzl  showed that triangle range queries can be solved in time using linear space but this holds only in the ...