A certified conflict locator for the incremental maintenance of the Delaunay graph of semi-algebraic sets

A certified conflict locator for the incremental maintenance of the Delaunay graph of semi-algebraic sets Fran¸cois Anton, Department of Computer Science, University of British Columbia, 201-2366 Main Mall, Vancouver, B.C., Canada, V6T 1Z4 Abstract Most of the curves and surfaces encountered in geometric modelling are defined as the set of solutions of a system of algebraic equations or inequalities (semi-algebraic sets). The Voronoi diagram of a set of sites is a decomposition of the space into proximal regions (one for each site). Voronoi diagrams have been used to answer proximity queries. The dual graph of the Voronoi diagram is called the Delaunay graph. Only approximations by conics can guarantee a proper continuity of the first order derivative at contact points, which is necessary for guaranteeing the exactness of the Delaunay graph. The central idea of this paper is that a (one time) symbolic preprocessing may accelerate the certified numerical evaluation of the Delaunay graph conflict locator. The symbolic preprocessing is the computation of the implicit equation of the generalised offset to conics. The certified computation of the Delaunay graph conflict locator relies on theorems on the uniqueness of a root in given intervals (Kantorovich, Moore-Krawczyk). For conics, the computations get much faster by considering only the implicit equations of the generalised offsets. Key words: Delaunay graph, semi-algebraic sets, conics, conflict locator 1. Introduction Most of the curves and surfaces encountered in geometric modelling are defined as the set of common zeroes of a set of polynomials (algebraic varieties) or subsets of algebraic varieties defined by one or more algebraic inequalities (semi-algebraic sets). Many problems from different fields involve proximity queries like finding the nearest neighbour, finding all the neighbours, or quantifying the neighbourliness of two objects. The retraction planning [´ OY85] problem (that addresses the optimal trajectory of a robot around obstacles) in robotics and spatial analysis and influence zones in Geographic Information Systems [VC90] are strongly linked to questions of proximity among real-world objects in real-world environments. The Voronoi diagram [Vor08] (see Fig. 1) of a set of sites is a decomposition of the space into prox- Email address: [email protected] (Franc¸ois Anton). imal regions (one for each site). The proximal region (or Voronoi zone) of a site is the locus of points closer to that site than to any other one. Voronoi diagrams allow one to answer proximity queries after a query point has been located in the Voronoi zone it belongs to. The Voronoi diagram defines a neighbourhood relationship among sites: two sites are neighbours if, and only if, their Voronoi regions are adjacent. The graph of this neighbourhood relationship is called the Delaunay graph. The Delaunay graph of sites in the plane satisfies the following empty circle criterion (see Fig. 2): no site intersects the interior of the circles touching (tangent to without intersecting the interior of) the sites that are the vertices of any triangle of the Delaunay graph (see Fig. 3). There have been attempts [OBS92] to compute Voronoi diagrams of curves by approximating curves by line segments or circular arcs, but the exactness of the Delaunay graph is not guaranteed [RF99a]. Indeed, the Voronoi diagram is very sensitive to the order of continuity at contact points (see [RF99a]). Only approxima- 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry Fig. 1. The Voronoi diagram (light) of a circle, an ellipse and a hyperbola (dark) Fig. 2. The 3 empty circles for the sites of Fig. 1 HYPERBOLA CIRCLE ELLIPSE Fig. 3. The Delaunay graph of the sites of Fig. 1 tions by conics can guarantee a proper continuity of the first order derivative at contact points, which is necessary for guaranteeing the exactness of the Delaunay graph [RF99a]. Other approximation algorithms have used a Newton-Raphson scheme to compute and classify Voronoi vertices for curves with a rational parameterisation [RF99a,RF99b]. These do not directly address the exactness of the Delaunay graph. 2. Preliminaries We will recall now the formal definitions of the Voronoi diagram and of the Delaunay graph. For this purpose, we need to recall some basic definitions. Definition 1 (Metric) Let Mbe an arbitrary set. A metric on Mis a mapping d:M×M→R+ such that for any elements a,b, and cof M, the following conditions are fulfilled: d(a, b) = 0 ⇔ a=b,d(a, b) = d(b, a), and d(a, c)≤d(a, b) + d(b, c).(M, d)is then called a metric space, and d(a, b)is the distance between aand b. Let M=RN, and δdenote the Euclidean distance between points. Let S={s1, ..., sm}⊂ M, m ≥2 be a set of mdifferent subsets of M, which we call sites. The distance between a point xand a site si⊂Mis defined as d(x, si) = infy∈si{δ(x, y)}. Definition 2 (Influence zone) For si, sj∈S, si(= sj, the influence zone D(si, sj)of siwith respect to sjis: D(si, sj) = {x∈M|d(x, si)< d (x, sj)}. Definition 3 (Voronoi region) The Voronoi region V(si,S)of si∈Swith respect to the set Sis: V(si,S) = !sj∈S,sj"=siD(si, sj). Definition 4 (Voronoi diagram) The Voronoi diagram of Sis the union V(S) = "si∈S∂V(si,S) of all region boundaries. Definition 5 (Delaunay graph) The Delaunay graph DG (S)of Sis the dual graph of V(S) defined as follows: – the set of vertices of DG (S)is S, – for each N−1−dimensional facet of V(S)that belongs to the common boundary of V(si,S)and of V(sj,S)with si, sj∈Sand si(=sj, there is an edge of DG (S)between siand sjand reciprocally, and – for each vertex of V(S)that belongs to the common boundary of V(si1,S),. . . ,V #siN+2 ,S$, with ∀k∈{1, ..., N + 2}, sik∈Sall distinct, there exists a complete graph KN+2 between the sik, k ∈{1, ..., N + 2}, and reciprocally. (see example on Fig. 3). Let us introduce the generalised offset and the generalised Voronoi vertex. We place ourselves in the affine space K2where K=Cfor the sake of introducing those notions in an easier way. While the R−generalised offset to νis the locus of the centres of circles of radius Rthat are tangent to ν, the true R−offset to νis the locus of the centres of circles of radius Rthat are tangent to νand do not contain any point of νin its interior (see Fig. 4). Definition 6 (generalised Voronoi vertex) A generalised Voronoi vertex of three semi-algebraic sets S1,S2, and S3is a point of intersection of the R−generalised offsets of S1,S2, and S3(see Exam- March 25-26, 2004 Seville (Spain) Fig. 4. The strophoid and its true (left) and generalised (right) offsets Fig. 5. A generalised Voronoi vertex (dot) of three conics (thick lines) ple on Fig. 5). 3. The Delaunay graph conflict locator for semi-algebraic sets Let X1, ..., XN+2, be semi-algebraic sets [BR90,BCR98]. A semi-algebraic set Xiis defined as: !si j=1 "ri,j k=1 #x∈RN|fi,j,k ⋆i,j,k 0$, where fi,j,k is a polynomial with real coefficients in the variables xi1, ..., xiNand ⋆i,j,k is either <or =, for i= 1,2,3,4, j= 1, ..., siand k= 1, ..., ri,j. The Delaunay graph conflict locator determines which ones of the maximal dimensional facets of the Delaunay graph of N+ 1 semi-algebraic sets X1, ..., XN+1 would be changed by the addition of the semi-algebraic set XN+2. Let us assume without loose of generality that each "ri,j k=1 #x∈RN|fi,j,k ⋆i,j,k 0$for each Xiis defined by at least one non-trivial algebraic equation (i.e. different from the zero polynomial). If our starting assumption is not valid in the case we treat, we can make it valid by adding the equations corresponding to fi,j,k = 0 for each (i, j, k) such that jis the index of a component that is not defined as in the assumption and iis the index of the semi-algebraic set to which the component belongs. Let us denote Vias the intersection of all the V(fi,j,k) such that ⋆i,j,k is = for each i= 1,2,3,4. Let Nibe the normal space to Viat the point xi= (xi1, ..., xiN). Each fi,j,k defining Viinduces N−1 polynomials ni,j,k,l with l= 1, ..., N −1 that are the equations defining the normal to V(fi,j,k) at xi. A point q= (y1, ..., yN) belongs to Niif its coordinates satisfy all the equations of the normal spaces to V(fi,j,k) at xisuch that ⋆i,j,k is =. For a given q= (y1, ..., yN), let Mibe the the set of points mi= (zi1, ..., ziN)∈Xisuch that q belongs to the normal space to Viat the point mi. In the general case, each set Miis a finite set of points. However, if Vicontains a portion of hypersphere P HS (q, ρ) centered on q, then Micontains that portion of hypersphere. To get in all cases a finite set of points miof Vi, we use Si=Miwhen Miis finite, and Si"P HS (q, ρ) = {wi}for an arbitrary point wiof P HS (q, ρ) when Vicontains a portion of hypersphere P HS (q, ρ) centered on q. We are now able to write the system of algebraic equations and inequalities that define the outcome of the Delaunay graph conflict locator. Let us consider the map π:K3N→KNdefined by π(xi, q, mi) = q. The point qis at the distance rfrom the point xiif, and only if, the distance between qand xiis r. This is expressed algebraically by the equation di(q, xi) = (y1−xi1)2+...+(yN−xiN)2−r2= 0. The generalised r-offset Oito Xiis the image by πof the points of K3Ndefined by the following system of equations and inequalities:                            ∃j∈[1, si],∀k∈[1, ri,j],                      fi,j,k (xi)⋆i,j,k 0 if ⋆i,j,k is “ = ”,          di(xi, q) = 0 ∀l= 1, .., N −1, ni,j,k,l (xi, q) = 0 fxi1(xi)&= 0 or . . . or fxiN(xi)&= 0 The true r-offset to Xiis obtained as the difference of the generalised r-offset Oito Xiand the union of each one of the images by πof the semialgebraic sets defined by the following system of equations and inequalities for each point miof Si:                            ∃j∈[1, si],∀k∈[1, ri,j],                      fi,j,k (mi)⋆i,j,k 0 if ⋆i,j,k is “ = ”,          f(mi) = 0 ∀l= 1, .., N −1, ni,j,k,l (mi, q) = 0 d(mi, q)<0 It is obvious that a true Voronoi vertex of 20th European Workshop on Computational Geometry Running time above systems generalised offsets General Solve 6 min 38 s 12 min 37 s Gradient Solve 2 h 56 min 10 s 2 min 26 s Hessian Solve 20 h 17 min 42 s 3 min 42 s Table 1 Some running time results for ellipses X1, ..., XN+1 is a point of intersection of the true r−offsets to X1, ..., XN+1 respectively. A true Voronoi vertex of X1, ..., XN+1 is at the distance Rfrom XN+2, or alternatively, a true Voronoi vertex of X1, ..., XN+1 belongs to the true R−offset to XN+2. Consider the N+ 2−dimensional points whose first Ncoordinates are the coordinates of a true Voronoi vertex of X1, ..., XN+1, and the remaining two are the distances rbetween that true Voronoi vertex and X1, ..., XN+1, and Rbetween that true Voronoi vertex and XN+2. The Delaunay graph conflict locator should report all the true Voronoi vertices such as the corresponding N+ 2−dimensional points satisfy R−r < 0. We have evaluated the Delaunay graph conflict locator without solving any intermediary system by using an interval analysis based library (ALIAS [Mer00]) for solving zero-dimensional systems of equations and inequalities. The certified computation of the Delaunay graph conflict locator relies on theorems on the uniqueness of a root in given intervals (Kantorovich and Moore-Krawczyk). This computation uses a bisection process on one or all the variables using either only the equations of the system, or using the Jacobian of the system (Moore-Krawczyk test for finding “exactly” the solutions), or using the Jacobian and the Hessian of the system (with Kantorovich, Moore-Krawczyk tests). We first used ALIAS on the above system of algebraic equations and inequalities that specify the Delaunay graph conflict locator for semialgebraic sets. Then for conics, we used ALIAS on the system simplified by replacing the equations fi, niand diof the conics, normals and distances between the points on the conics and the true Voronoi vertex by the implicit equations of the generalised offsets to the conics (see [Ant04]). This induces much faster computations (see Table 1). 4. Conclusions We have presented what we believe is the first certified conflict locator for the incremental maintenance of the Delaunay graph for semi-algebraic sets. Further research will try to improve the running time of the computations. References [Ant04] Fran¸cois Anton. Voronoi diagrams of semialgebraic sets. PhD thesis, University of British Columbia, January 2004. [BCR98] Jacek Bochnak, Michel Coste, and Marie- Fran¸coise Roy. Real algebraic geometry. Springer- Verlag, Berlin, 1998. Translated from the 1987 French original, Revised by the authors. [BR90] Riccardo Benedetti and Jean-Jacques Risler. Real algebraic and semi-algebraic sets. Hermann, Paris, 1990. [Mer00] Jean-Pierre Merlet. Alias: an interval analysis based library for solving and analyzing system of equations. In SEA, Toulouse, France, 14–16 June 2000. [OBS92] Atsuyuki Okabe, Barry Boots, and K¯okichi Sugihara. Spatial tessellations: concepts and applications of Vorono¨ı diagrams. John Wiley & Sons Ltd., Chichester, 1992. With a foreword by D. G. Kendall. [´ OY85] Colm ´ O’D´unlaing and Chee-K. Yap. A “retraction” method for planning the motion of a disc. J. Algorithms, 6(1):104–111, 1985. [RF99a] Rajesh Ramamurthy and Rida T. Farouki. Voronoi diagram and medial axis algorithm for planar domains with curved boundaries. I. Theoretical foundations. J. Comput. Appl. Math., 102(1):119–141, 1999. Special issue: computational methods in computer graphics. [RF99b] Rajesh Ramamurthy and Rida T. Farouki. Voronoi diagram and medial axis algorithm for planar domains with curved boundaries. II. Detailed algorithm description. J. Comput. Appl. Math., 102(2):253–277, 1999. [VC90] Christine Voiron-Canicio. Analyse spatiale et analyse d’images par la morphologie math´ematique. RECLUS, 1990. [Vor08] Georgi¨ı Feodosevich Vorono¨ı. Nouvelles applications des param`etres continus `a la th´eorie des formes quadratiques. deuxi`eme m´emoire. recherches sur les parall´elo`edres primitifs. premi`ere partie. partition uniforme de l’espace analytique `a ndimensions `a l’aide des translations d’un mˆeme poly`edre convexe. Journal f¨ur die reine und angewandte Mathematik, 134:198–287, 1908.