Geometric Searching
Bernard Chazelle · Cambridge University Press eBooks · 2000
To answer specific queries regarding a large collection of geometric data is what geometric searching is all about. The data could be a road map, the query could be a pair of coordinates obtained from a GPS navigational system, and the expected reply could be the name of the road that the car is on. With increasing frequency, such geometric databases can be found tucked into car dashboards, or at least tucked away in people's imagination of what a dashboard should look like. Range searching typically refers to more complex queries, eg, how many towns of more than 10,000 people can be found within 100 miles of Natchez, Mississippi? Or more challenging still: What is the library nearest you with a copy of this book? This chapter highlights one of the finest vehicles for divide-and-conquer in computational geometry. It is a versatile data structure known as an ε- cutting . Suppose that we are given a set H of n hyperplanes in R d . We wish to subdivide R d into a small number of simplices, so that none of them is cut by too many hyperplanes. Specifically, given a parameter ε > 0, a collection C of closed full-dimensional simplices is called an ε-cutting (Fig. 5.1) if: (i) their interiors are pairwise disjoint, and together they cover R d (hence, some are unbounded); (ii) the interior of any simplex of C is intersected by at most ε n hyperplanes of H .