O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

27

Approximate Geometric Query Structures*

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

27.7Maximum-Spread k-d Trees

Acknowledgments

References

27.1Introduction

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 O(nlogn) time using linear space but this holds only in the ...

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

Start Free Trial

No credit card required