Farthest-point Voronoi diagram & Smallest enclosing circle

Current action:


Farthest-point Voronoi diagram and smallets enclosing circle

The smallest enclosing circle is the circle with the smallest possible radius that, given a set of points, it contains all of them. It is known that the circumference C border of the smallest enclosing circle of a finite set P of points always crosses by two points of P, that are diametrically opposed, or by three of the points of P. In both cases, the points than determine the circumference C equidistan from its center. Therefore, the center of the smallest enclosing circle is, either inside an edge of the farthest-point Voronoi diagram from P (in which case C is determined by two diametrically opposed points) or coincides with one of the vertices of that diagram (case where C is determined by three points). In both cases, the points of P that determine the circle are vertices of the convex hull of P.

What is the smallest enclosing circle?

The algorithm to construct the smallest enclosing cirlce is as follows: Given a set of n points P = {p1,p2 ,...,pn} ⊂ ℝ2, it starts computing its convex hull CH = {v1,...,vh, where C is ordered so that next(vi) and prev(vi are the vertexs of CH previous and next to vi ordered counterclockwise, respectively. We denote as radius(p,q,r) the radius of the circumference that cross by the three points p, q and r, if they are different. If two points are the same, radius(p,q,r) denotes the half of the distance between the two different points. Finally, angle(p,q,r) indicats the angle formed by the segments pq and qr. Throughout the algorithm, it will always be the case that p ≠ q and r ≠ q, but it can happen that p = r.

The algorithm analyzes the circles determined for every three consecutive vertexs from CH, takes the biggest in terms of radius (and, in case of draw, in terms of angle), and it descards it if the three points that generates it form an obtuse triangle.

What is the farthest-point Voronoi diagram?

The farthest-point Voronoi diagram of a finite set of points P (usually called "sites"), is a decomposition of the plain in regions. Each region is characterized by being the geometric location of the points which the farthest site is the site itself. Only the vertexs of the convex hull of P have a non-empty farthest-point Voronoi region assosiated.

The farthest-point Voronoi diagram of P can be represented as a flat graph. In fact, the diagram in not a graph in the affine space, since some of its edges are semi-rects. In particular, the diagram contains a semi-rect for each pair of consecutive vertices of the convex hull of P, semi-rect that is a part of the perpendicular bisector of the pair of points. However, the diagram can be represented as a graph by considering that all the semi-rects share a Voronoi vertex at infinity. This, considered as a flat graph, it is stored in a Doubly Connected Edge List (DCEL) in which the vertices of degree 1 indicates the direction of a semi-rect of the 1-skeleton of the diagram, while the rest of vertices, all of them of degree greater than or equal to 3, correspond to vertices themselves in the Voronoi diagram.

We denote by v(p) a point on the bisector of p and next(p), where p is a vertex of the convex hull of the given set of points P. Initially, v(p) is a point on the bisector of p and next(p) "at infinity" and to the right of the segment pnext(p)


Furthermore, as already mentioned, we can represent the farthest-point Vornoi diagram as a flat graph. Therefore, we will denote that FVD = (K,E), where K is the set of vertices of the farthest-point Voronoi diagram and A is the set of edges of the farthest-point Voronoi diagram. The algorithm to construct the farthest-point Voronoi diagram is similar to the one used in the calculation of the smallest enclosing circle, with a simple extension, which consists of: given the set of points CH = v1,...,vk computed for the smallest enclosing circle, the algorithm analyzes the circles determined by each three consecutive vertices of the CH, takes the biggest one in terms of radius (and, in case of a tie, in terms of angle), as we saw in the construction of the smallest enclosing circle. Once this circle C is obtained, we have p, which is the point such that prev(p),p,next(p) forme the cirlce C, with center c. Having the center of the circle c and the points p that forms it, we add the center c to the set of vertices of the farthest-point Voronoi diagram K and add to E the edges incident to this point c from the point v(p) and the one before, v(prev(p)). Therefore, we would have that K = K ∪ c and E = E ∪ (c, v(p)) &cup(c, v(prev(p))). By adding this new porint c to the set of vertices, the bisector v(p) is no longer a point "at infinity" as stated before, but is now the new point c. Also, we must remove p from the set of points CH, CH = CH - {p}.

As the treated points are removed from CH, there will be a time when circles can not be generated since there will only be 2 points left in CH. At this point, add to the set E the edge formed by the points v(q) and v(next(q)): E = E &cup (v(q), v(next(q))).

What are the Halton sequences?

The Halton sequences are very useful for generating random points on the plane (actually pseudo-random). This sequences are constructed with a deterministic method based on the coprime numbers. An example of constructing point in the square (0,1) X (0,1) ⊂ ℝ2 with bases 2 and 3, respectively, is as follows:

To generate the sequence of base 2, the space (0,1) is divided recursively in two halves, then four parts, then eight parts, etc.

1/2, 1/4, 3/4, 1/8, 5/8, 1/16, 9/16, ...

Similraly, in base 3 the interval (0,1) is recursively divided into thirds, obtaining the sequence:

1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 1/27, ...

Combining both sequences the following points are obtained in the square (0,1) X (0,1):

(1/2,1/3), (1/4,2/3), (3/4,1/9), (1/8,4/9), (5/8, 7/9) (3/8,2/9), (1/16,5/9), (9/16,1/27), ...