algorithms

Techniques We describe in some detail five main techniques that have emerged for generalized inter- section searching over the past few years. Briefly, these include: an approach based on a geometric transformation, an approach based on generating a sparse representation of the input, an approach based on persistent data structures, a generic method that is applicable to any reporting problem, and an approach for searching on a subset of the input satisfying a specified range restriction. We illustrate each method with examples. A Transformation-Based Approach We first illustrate a transformation-based approach for the reporting and counting problems, which converts the original generalized reporting/counting problem to an instance of a related standard reporting/counting problem on which efficient known solutions can be brought to bear. We illustrate this approach by considering the generalized 1-dimensional range searching problem. Let S be a set of n colored points on the x -axis. W

Nearest Neighbor Searching Nearest neighbor searching is an important problem in a variety of applications, including knowledge discovery and data mining, pattern recognition and classification, machine learning, data compression, multimedia databases, document retrieval, and statistics. We are given a set S of objects in some space to be preprocessed, so that given a query object q , the closest object (or objects) of S can be reported quickly. There are many ways in which to define the notion of similarity. Because the focus of this chapter is on geometric approaches, we shall assume that proximity is defined in terms of the well known Euclidean distance. Most of the results to be presented below can be generalized to any Mi n kow ski (or L m ) metric , in which the distance between two points p and q is defined to be where m ≥ 1 is a constant. The case m = 2 is the Euclidean distance, the case m = 1 is the Manhattan distance, and the limiting case m = ∞ is the max distance. In

Triangulations In geometric data processing, structures that partition the geometric input, as well as connectivity structures for geometric objects, play an important role. Versatile tools in this context are triangular meshes , often called triangulations . A triangulation of a geometric domain such as a polygon in R2 or a polyhedron in R3 is a partition into simplices that meet only at shared faces. A triangulation of a point set S is a triangulation of the convex hull of S , such that the vertices in the triangulation are exactly the points in S . In the following sections, we first discuss the most famous of all triangulations, the Delaunay triangulation. We then address triangulations of polygons and polyhedra in R3. Finally we describe a recent generalization of triangulations: the pseudo-triangulation. Delaunay Triangulation In this section we provide additional detail on the Delaunay triangulation of a set S = { s 1 ,.. . , s n } of points in R d , which was introduce