Approximate Geometric Query Structures

Authored by: Christian A. Duncan , Michael T. Goodrich

Handbook of Data Structures and Applications

Print publication date:  March  2018
Online publication date:  February  2018

Print ISBN: 9781498701853
eBook ISBN: 9781315119335
Adobe ISBN:


 Download Chapter



Specialized data 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 [1] showed that triangle range queries can be solved in δ ( p , q ) = ( ∑ i = 1 d | p i − q i | m ) 1 m . time using linear space but this holds only in the plane. In higher dimensions, the running times go up dramatically, so that, in general, the time needed to perform an exact simplex range query and still use small linear space is roughly Ω(n 1−1/d ), ignoring logarithmic factors [2]. For orthogonal range queries, efficient query processing is possible if superlinear space is allowed. For example, range trees (Chapter 19) can answer orthogonal range queries in O(log d−1 n) time but use O(n log d−1 n) space [3].

Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.