Computational Geometry,Proximity and Location:Proximity Structures
Proximity Structures
Proximity structures arise from numerous applications in science and engineering. It is a fundamental fact that nearby objects tend to exert a greater influence and have greater relevance than more distant objects. Proximity structures are discrete geometric and graph structures that encode proximity information. We discuss a number of such structures, in- cluding Voronoi diagrams, Delaunay triangulations, and various geometric graph structures, such as the relative neighborhood graph.
The Voronoi diagram of a set of sites S is a partition of space into regions, one per site, where the region for site s is the set of points that are closer to s than to any other site of S. This structure has been rediscovered and applied in many different branches of science and goes by various names, including Thiessen diagrams and Dirichlet tessellations.
Henceforth, we consider the most common case in which the sites S consist of a set of n points in real d-dimensional space, Rd, and distances are measured using the Euclidean metric. The set of points of Rd that are closer to some site s ∈ S than any other site is called the Voronoi cell of s, or V (s).
(See Figure 63.8.)
The union of the boundaries
of the Voronoi cells is the Voronoi diagram of S, denoted Vor (S). Observe that the set of points of Rd that are closer to s than some other site t consists of the points that lie in the open halfspace defined by a plane that bisects the pair (s, t). It follows that each Voronoi cell is the intersection of n − 1 halfspaces, and hence, it is a (possibly unbounded) convex polyhedron. A Voronoi diagram in dimension d is a cell complex whose faces of all dimensions are convex polyhedra. In the plane a Voronoi diagram is a planar straight line graph with possibly unbounded edges. It can be represented using standard methods for representing polygonal subdivisions and cell complexes (see Chapter 17).
The Voronoi diagram possesses a number of useful geometric properties. For example, for a set of points in the plane, each edge of the Voronoi diagram lies on the perpendicular bisector between two sites. The vertices of the Voronoi diagram lie at the center of an empty circle passing through the incident sites. If the points are in general position (and in particular if no four points are cocircular) then every vertex of the diagram is incident to exactly three edges. In fact, it is not hard to show that the largest empty circle whose center lies within the convex hull of a given point set will coincide with a Voronoi vertex. In higher dimensions, each face of dimension k of the Voronoi diagram consists of the points of Rd that are equidistant from a subset of d − k + 1 sites, and all other sites are strictly farther away. In the plane the combinatorial complexity of the Voronoi diagram is O(n), and in dimension d its complexity is Θ(nId/2l).
Further information on algorithms for constructing Voronoi di- agrams as well as variants of the Voronoi diagram can be found in Chapter 62. Although we defined Voronoi diagrams for point sites, it is possible to define them for any type of geometric object. One such variant involves replacing point sites with line segments or generally the boundary of any region of the plane. Given a region P (e.g., a simple polygon), the medial axis is defined to be the set of centers of maximal balls contained in P , that is, balls con- tained in P that are not contained in another ball in P [32]. The medial axis is frequently used in pattern recognition and shape matching. It consists of a combination of straight-line segments and hyperbolic arcs. It can be computed in O(n log n) time by a modification of Fortune’s sweepline algorithm [39]. Finally, it is possible to generalize Voronoi diagrams to other metrics, such as the L1 and L∞ metrics (see Section 63.4).
The Delaunay triangulation is a structure that is closely related to the Voronoi diagram. The Delaunay triangulation is defined as follows for a set S of n point sites in the plane.
Consider any subset T ⊆ S of sites, such that there exists a circle that passes through all the points of T , and contains no point of S in its interior. Such a subset is said to satisfy the empty circumcircle property. For example, in Figure 63.9(a), the pair {p, q} and triple {r, s, t} both satisfy the empty circumcircle property. The Delaunay triangulation is defined to be the union of the convex hulls of all such subsets. It can be shown that the result is a cell complex. Furthermore, if the points are in general position, and in particular, no four points are cocircular, then the resulting structure is a triangulation of S. (If S is not in general position, then some faces may have more than three edges, and it is common to complete the triangulation by triangulating each such face.) A straightforward consequence of the above definition is that the Delaunay triangulation is dual to the Voronoi diagram. For example, Figure 63.9(b) shows the overlay of these two structures in the plane.
Delaunay triangulations are widely used in practice, and they possess a number of useful properties. For example, among all triangulations of a planar point set the Delaunay trian- gulation maximizes the minimum angle. Also, in all dimensions, the Euclidean minimum spanning tree (defined below) is a subgraph of the Delaunay triangulation. Proofs of these facts can be found in [31].
In the plane the Delaunay triangulation of a set of points has O(n) edges and O(n) faces. The above definition can be generalized to arbitrary dimensions. In dimension d, the Delaunay triangulation can have as many as Θ(nId/2l) faces. However, it can be much smaller. In particular, Dwyer [34] has shown that in any fixed dimension, if n points are drawn from a uniform distribution from within a unit ball, then the expected number of simplices is O(n).
There is an interesting connection between Delaunay triangulations in dimension d and convex hulls in dimension d + 1. Consider the lifting map f : R2 → R3 defined f (x, y) = (x, y, x2 + y2). This projects points in the plane onto the paraboloid z = x2 + y2. Given a planar point set S, let St denote the set of points of R3 that results by applying this map to each point of S. Define the lower hull of St to be the set of faces whose outward pointing normal has a negative z coordinate. It can be shown that, when projected back to the plane, the edges of the lower convex hull of St are exactly the edges of the Delaunay
Although there exist algorithms specially designed for computing Delaunay triangulations, the above fact makes it possible to compute Delaunay triangulations in any dimension by computing convex hulls in the next higher dimension. There exist O(n log n) time algorithms for computing planar Delaunay triangulations, for example, based on divide- and-conquer [70] and plane sweep [39]. Perhaps the most popular method is based on randomized incremental point insertion [45]. In dimension d ≥ 3, Delaunay triangulations can be computed in O(nId/2l) time through randomized incremental point insertion [27].
Other Geometric Proximity Structures
The Delaunay triangulation is perhaps the best known example of a proximity structure. There are a number of related graph structures that are widely used in pattern recognition, learning, and other applications. Given a finite set S of points in d-dimensional Euclidean space, we can define a graph on these points by joining pairs of points that satisfy certain neighborhood properties. In this section we will consider a number of such neighborhood graphs.
Let us first introduce some definitions. For p, q ∈ Rd let dist(p, q) denote the Euclidean distance from p to q. Given positive r ∈ R, let B(p, r) be the open ball consisting of points whose distance from point p is strictly less than r. Define the lune, denoted L(p, q), to be the intersection of two balls both of radius dist(p, q) centered at these points, that is,
Comments
Post a Comment