With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

27

Christian A. Duncan

Quinnipiac University

Michael T. Goodrich

University of California, Irvine

27.1Introduction

27.2General Terminology

27.3Approximate Queries

27.4Quasi-BAR Bounds

27.5BBD Trees

27.6BAR Trees

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 [1] showed that triangle range queries can be solved in $math$ time using linear space but this holds only in the ...