Voroioi Diagraas and Arrang?enta Herbert Edelsbrunner* Raimund Seidel Th 85-669 March 1985 Department of Computer Cornell University Ithaca* New York 14853 Science * Institute fur Informationsverarbeitung, Technical University of Graz, Schiesstattgasse 4A, A-8010 Graz1 AUSTRIA. < "I Figure 1.1: AVoronci Diagram Voronol Diagrams and Arrangements Herbert Ede?abrsnner Institute fur Informationsverarbeitung Technical University of Graz Schiesstattgasse 4A A-SO10 Graz AUSTRIA Raimund SeideL Computer Science Department Cornell University Ithaca NY. 14853 U.SA. Abstract: We propose a uniform and general framework for defining and dealing with Voronoi Diagrams. In this framework a Voronoi Diagram is a partition of a domain D induced by a finite number of real valued functions on D. Valuable insight can be gained when one considers how these real valued functions partition D x R. With this view it turns out that the standard Euclidean Voronoi Diagram of point sets in Rd along with its order-k generali- zations are intimately related to certain arrange- ments of hyperplanes. This fact can be used to obtain new Voronoi Diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union prob? lems. I. Introduction Figure 1.1 depicts a type of diagram that is known under such names as Dirichlet tesselation, Thiessen polygons, or as we call it, Voronoi Diagram. The formation rule for such a diagram is simple. The location of a finite number of "sites" is known. For each "site" 9 one wants to form the region of all points for which 8 is the nearest among the finite set of "sites". If `nearest" is understood with respect to the Euclidean distance measure, then for each "site" its associated region is polygonal. In the context of computational geometry Voronoi Diagrams were first introduced in a paper by Hoey and Shamos [sh?HJ. The usefulness of the Voronoi Diagram (from now on VoD) for solving a large number of problems, the fact that it can be constructed efficiently, and maybe also its aesthetically pleasing appearance subsequently kindled the interest of many researchers. They tried to apply the VoD to other problems, and if this was not possible directly, attempted to adapt and generalize the notion of a VoD appropriately. Among the genera? izations are higher order VoDs (Sh-?,[L76i, VoDs of line segments and/or circular arcs ?ryj,(L? DJ,[Ki,!?Li,tYapi, VoDs of point sets in Rd,d>2, IBowl,fWal, weighted Voronoi Diagrams IA-El, power diagrams, or VoDs with respect to the Laguerre geometry IAI,[nMl, VoDs with respect to the L' metric, 1 C< (a),tb,?,?> fa C<(b),(c),(a)> ?? C<(a?(bJ,(c)> I C<(b),(a),(c ?c C Figure 2.1: The 2Ievel of an arrangement C < (a),fb,c),?> Figure 2,2: The 2?beIt of an arrangement number of real valued functions on D. In section 3 we show how VoDs can be defined on any domain D via finite sets of real valued functions. We demonstrate how VoDs are related to arrangements and we discuss a number of examples in some detail. Section 4 deals with higher order and higher degree VoDs and their relationship to arrangements which turns out to be particularly attractive. Sec- tion 5 contains a short outline how the formalism of arrangements can be used to solve certain intersec- tion and union problems. In the last section we cuss possible directions for further research. II. Arrangements In this section we consider the interactions among a finite number of real valued functions on an arbitrary domain D. The structure imposed on D x R by such a finite set of functions promises to be an interesting obiect of study, provided the domain D and and functions as well as their interactions are restricted appropriately. For instance, when D = Rd and all the functions are afline, the structure of D x R has been studied to a fair extent as s?called hyperplane arrangement 1G711,[G721. Similarly, in a slight generalization, when D = Rd and all functions are continuous and satisfy certain finite intersection axioms, the structure imposed on D >(R has been studied as s?called arrangement of pseudohyperplanes, and also in the context of oriented matroids iNil. In this section we do not intend to study the effect of any other function or domain restriction. We rather want to give some general definitions and results in order to provide a convenient frame- work to argue about Voronoi Diagrams, the main topic of this paper. Let D be some domain. For a real valued function f on D we call the subset of D xR f+=((:,r) If(?)>r ? the lower hemiepace of I, the set f-=?(r,r) If(:) , where = minus(?) , Ec = zero(?) , and E+ --H plus(I). In a natural way itj defines an equivalence relation on DxR, making two points I and z equivalent iff itj (I) = it?(z). We call the partition of DxR induced by it? an f--Harrangement. We call each equivalence class of an f-arrangement a cell. Each cell can be uniquely named by a partition of E: = ii E DxR I ?i(I) = Equivalently, a cell can be represented as an inter- section: = A fJ fl fl fe0 fl A fe+ E I Ct0 E As there are only a finite number of partitions of the index set E, the number of cells in an fi- arrangement is finite and hence f-arrangements can be studied as combinatorial objects. We call a cell C a full cell iff E0= S. For an integer k, O a k-belt cell iff El = Ic. We call a cell C a k4e?l cell iff El < I: and El + E0l > k. Note that a cell is in E0l different levels. Figure 2.1 shows the 2-level cells of an arrangement of 3 real valued functions on R. Figure 2.2 depicts the 2- belt cells of the same arrangement. Note that cells are not necessarily `?connected". If f and gg are two indexed collections of real valued functions on a common domain D, then we call fi and g order-eqw?alent iff for all z E D and for every pair i,j E E sign(f,(z) --H f?(:)) --H sign(g?(r) --H If two function collections fi and g are order- equivalent, then the f-arrangement and g- arrangement of DXR are isomorphic in the follow- ing sense: Lemma 2.1: Let f and g collections on Let be a partition of E. be two order-equivalent function (i) There exists a non-empty cell in the f-arrangement iff there exists a non-empty cell C' in the fl?arrangement. Moreover, (ii) proj( C ) = proj( C'<:??o?+> ), where for C C DxR the expression proj(C) denotes ( : ED (z,r) E C for some r E R ). Proof: To prove both (i) and (ii) it suffices to show that for every I = (:,r) E DxR there exists an r' E R such that :r1((r,r)) --H Let = :r1((z,r)). Because of the order-equivalence between f and g? we know that for e E E?,e+ E E+ and e,e' E E0 the relations g,4r) < g,(x) < g,+(r) and g,(x) = g,'(r) hold. Now let 1 =max( g,(x) e EE-uE0), t' =min( g,(z) le EE+UE0l,and choose r' = 1(1 + t'). 2 forces 7r1((x,r)) = Such a choice of r' Q.E?D. in the remainder of this section we consider two important classes of arrangements. Let the domain D be Rd for some d>1. For e E E let f, be an affine function given by fe(x)= +be, where ae E Rd, be E R, and denotes the usual scalar product between vectors. The surface f?0 of such an affine function is usually called a (?tnon?vertical??) hyperpiane in Rd xR = Rd+l. The upper and lower hemispaces f?+ and fe are in this case usually referred to as upper and lower (open) halfspaces. The f.arrangement of Rd+1 is usually called an arrangement of hyperplanee, and is, as mentioned in the beginning of this section, a fairly well studied mathematical object (G721,!zl. Every cell in an arrangement of hyperplanes is the intersection of a finite number of halfspaces and hyperplanes and hence a pot1Ihe dron In the literature of hyperplane arrange- ments one usually considers the topological closure of a cell C with --H fl (fe?Uf,? fl E E fl fl (f,+Ufe? fl is usually called a arrangement. Faces are assigned namely the dimension of the n fe0 E E0 face of the a dimension, smallest flat containing the face. It is known that the number of faces in an arrangement of n hyperplanes in Rd+l is o(nd+1). More specifically, let c,(d,n) denote the maximum possible number of faces of dimension i in an arrangement of n hyperplanes in Rd Fact 2.1: ?Z? c,(d,n) --H ? t?fJI?ii for O r for e E 7" which is the same as saying `r1((z,r)) = , which in turn holds if and only if(:,r) E C<.,r.r,>. Q.E.D. For some e E E consider the V-region V(,) in Theorem 3.1 and Lemma 2.1 immediately yield the VOD(f:). V(,) contains all points : E R2 with important the property that Corollary 3.1: e E E f,(:)=m?inf?(r) ) = e ), If I: and g? are order-equivalent function collec- tions, then VOD(/:) --H VOD(g:). or, in other words, V(,) contains all r with /,(:) < f?(Z) for all i E E, i,'e, i.e. all z with d(p,,:) < d(p?,z) for all i E E, i#e. Thus V(,) is exactly the interior of what is usually considered the Voronoi region of point p,. Similarly, if a V-cell V(,,j) exists inVOD(f:) for some pair i,j E E, then this V-cell, by the same reasoning as above, contains all z with d(p,,x) = d(p1,r) < d(pe,z) for all e E E, i,'e $i. Thus V(,,j) is exactly the relative interior of the edge between the two V-regions V(?) and V(j). Finally, V-cells of the form Vr with 7' > 3 turn out to be the vertices in the traditional VoD (see Figure 3.1). The reader may convince himself that with the right choice of functions other kinds of VoDs, such as Voronoi Diagrams with respect to the L? metric (Lsol, VoDs of line segments (L-Dl,IKi,[S L],?apj, and weighted VoDs ?A-E1, can be expressed using our functional formalism. An almost trivial but very important obser- vation is the fact that for a function collection f: the Voronoi Diagram of f in D and the fE- arrangement in D xR are intimately related. We have the following Theorem 3.1: Let f be a collection of real valued functions on a domain D, and let ?,`T c E and 7" =E- 7' Vr is a V-cell in VOD(f5) iff C is a cell in the f?-arrangement. Moreover, Vr --H proj( C<.,r?r >)- (Note that the cells C with S --H ?? 7' are exactly the I-level cells.) Applying Theorem 3.1 to the cases of collections of affine functions or collections of quadratic functions on Rd and using the algorithmic facts stated in sec- tion 2 we obtain the following important unifying algorithmic result. Theorem 3.2: Let D = Rd for some d > 1. Let 1 be a collection of affine functions on Rd given by = + be , ?e ERd , 6, ER or let 1 be a collection of quadratic functions of the form --H (x?p,)?A(x?p,)+ te Pe E Rd , e E R, where A is a d x d real symmetric matrix. VOD(f:) can be constructed in worst case time O(nlogn) for d --H 1,2 and 0(nRd+l)/2l) for d >3. This is optimal for odd d and for d = 2. Proof: By Theorem 3.1 and Corollary 3. lit suffices to con- struct the i-level cells in an arrangement of hyper- planes in Rd+1, which can be done in the given time bounds by Fact 2.4. Q.E.D. Theorem 3.2 is quite important because it unifies a number of algorithmic results in the literature about different kinds of VoDs. Below we give examples of what kind of planar VoDs are gen- erated by collections of quadratic (or, equivalently, affine) functions. Example 3.1: (ordinary Euclidean VoD ish-Hi) For each ` E E let p, be a point in R2. Let I constructing the polyhedron formed by the intersec- tion of all lower halfspaces, [B781,[P-H1,?-M1,[s1 imply Fact 2.4: All i-level faces (or equivalently all n-level faces) of an arrangement of n hyperplanes in Rd+l can be found in time O(nlogn) for d = 1,2 O(n Rd+1)/21) for d > 3. This is worst case optimal for odd d and d --H 2. Much less is known about complexity bounds for constructing all k -level faces for arbitrary k. Fact 2.5: [El All k -level faces of an arrangement of n planes in R3 can be found in time O( ?logn lk(n,3)). This concludes our elaboration on the first class of examples of f1-arrangements. Our second class of examples deals with para- boloids. Let again the domain D of the functions be Rd, d>L Let A be a dxd symmetric real matrix. For e E E let g, be a quadratic function of the form --H (x?pS)?A(X?Pf)+ ti, where p? E Rd, and t? E R. The surface g?0is usu- ally called a paraboloid and we thus call such g- arrangement in Rd+I a paraboloid arrengement. To our knowledge paraboloid arrangements per se have not been studied in the literature. However, as the following important lemma shows, there is really no need to do so. Lemma 2.2: For e E E let gf be quadratic functions defined by --H (:?pe)TA(:?pe) + te p? E Rd and tf E R. For e E E let f? he affine functions defined by fe(s) --H <:,sc> + b? at --H 2API , --H pt?Apc + t?. The collection of functions fg and g1 are order- equivalen? sign(ft(r)?!j(:)) --H sign(g.(s)--Hg,(:)). However, it can be checked easily that in our case even --H g(:)--Hg1(:) --H (p,?Ap# + t,) --H (pjTApj + tj) + 2(p1?p,)TA: holds. Lemmas 2.1 and 2.2 imply that the para- boloid arrangement and the hyperplane arrang? ment generated by g and 1, respectively, are combinatorially indistinguishable with respect to their cell structure. As a matter of fact, the even stronger relation holds that every cell in the hyper- plane arrangement is the homeomorphic image of the corresponding cell in the paraboloid arrange ment under the differentiable and invertible ma? ping FA of Rd+l onto itself defined by FA((X,Z)) --H where: E Rd and z E R. In other words, FA `?warps" Rd+l in such a way that all paraboloids generated by the matrix A are flattened out into hyperplanes, but all intersection patterns are preserved. Thus all the results stated above about hyperplane arrangements apply to par- aboloid arrangements as welL m. Voronoi Diagrams As in the previous section let E be a finite index set of n elements and let Ii --H ( If e E E ) be an indexed collection of real valued functions on some common domain D. Let R1 be a function from D to E defined by --H (e EE lA(s)--HminA(s)). El R1 induces in a canonical way an equivalence rela- tion Pi on D, where for :,; ED, 5 PI I ?R1(:)=R1(1). We call the partition of D induced by this equivalence relation PI the Voronoi Diagram on D witA respect to Is, for short VOD(f). The equivalence classes of the partition are called Voronoi celia or V-celia. We denote each V-cell by Vr, where T C E and Vr --H (sED R1fr)=r). A V-cell Vr with IT I --H 1 is sometimes also called a Voronoi region or V-region. This general, functional definition of Voronoi Diagrams might look somewhat startling and unorthodox to a reader only familiar with the usual definition of VoDL Thus it seems appropriate to show that for the right choice of functions 1, the Voronoi Diagram of Is obtained using our Proof: We have to show that for every : E Rd and any pair i,j E E Figure 3?1 denote the 2x2 identity matrix. For each e E E let g, be the quadratic function --H (2?p,)T1(2?p1). Note that g, (:) is the square of the Euclidean dis- tance function between p? and 2, iC. --H (/,(:))2, where/,(:)--H d(pt,:). Earlier we argued that VOD(!) is the traditional Euclidean Voronoi Diagram of the points p,. As the distance function is non.negative, the collection g is order-equivalent to 1, and hence VOD(g) is the traditional Euclidean Voronoi Diagram as well. Note 3.1: The ordinary Euclidean VoD is of such importance that it seems worthwhile to spell out again the geometric intuition that is hidden behind the formalism. For each e E E the function g? describes a paraboloid of rotation g, in R3 which is tangent to the :1-:?plane at point Pe? has its axis parallel to the :-axis, and "opens upward" towards z --H + 00. Imagine the set ( g?0 e E E ) of paraboloids in R3 penetrating each other. Furthermore, imagine each paraboloid to be opaque and having a unique colour. Finally, imagine an observer standing at 2 = --H00 looking in the positive ?-direction. The visible parts of the paraboloids would appear like the VoD of the point set ( p? e E E ) with each V-region coloured differently. Now imagine that the entire 3-space is "warped" by the function F,, with 22,) = (2i, 2g, Z --H 2?2 --H 222). Since the mapping F, leaves the 2 and ? coordi- nates invariant, and since it also does not change the difference in -coordinate of points with identi- cal ?1-r?coordinates, nothing changes for the observer at = --H00. He still sees the same coloured tiling of the plane. Finally, we want to point out that the planes 1,0 are not arbitrary planes in R3, but each ?,0 is the tangent plane to the "upside down" paraboloid of rotation q --H ((21,22,2) I z ??212?222) at point p,? which has the sanie 21 and :2 coordinates as p, but has z-coordinate --H. Example 3.2: (Euclidean furthest point VoD [Sh- HI) Let the set E and the matrix I be as in example 3.1. For e E E let again p, be a point in the plane and let g, be a function defined by For the collection g? of functions of this kind, VOD(g) turns out to be what has been tradition- ally known as the furthest point Voronoi Diagram of the planar point set ( p' e E E ). Note 3.2: One of the reasons why the Euclide?n closest point and furthest point Voronoi Diagram are of such importance is the usefulness of their geometric dual graphs, the socalled closest point and furthest point DeIa"nay triangutationa [Sh-H]. It seems worthwhile to point out that these triangulations can be naturally derived from the polyhedron P in the paraboloid construction in Note 3.1. Let X be the set of points ( p,' e E E ) on the upside down paraboloid q0 (as in Note 3.1). Let P. be the convex hull of X. Then the closest point Delaunay triangulation of the planar point set ( p, e E E ) is exactly the projection of the faces of P. which are "on top ?r' P., i.e., which could be seen by an observer at = + 00 looking in the negative z-direc?ion. Similarly, the furthest point Delaunay triangulation is exactly the projec- tion of the faces of P. which are "undernea'h", i.e. the faces visible to an observer at = --H00. that F, maps every para- Example 3.3: (Power Diagrams [Al' or VoDs in The point is, however, the "Laguerre geometry" IliNfi) boloid g?0 to the plane j,O, where = --H2 + . Again let I denote the 2x2 identity matrix. For e E E let p, = (:,,?) be a point in the plane and Thus what the observer at 2 = --H00 sees, is the pro let t, be a real number. Define functions g, by jection onto the :?:?plane of the boundary of the polyhedron P formed by the intersection of the g,(:) = (: p,)?1(2 --Hp,) + t,. lower halfspaces ( /,+ e E E ). Algorithmically, The VoD defined by the collection g of such func- of course, this means that in order to construct the tions was first discussed in the context of computa- VoD it suffices to construct the polyhedron P. A? tional geometry in [Al where it is called "power a matter of fact, if one analyzes Hoey and Shamos diagram", and in [I'??I where it is called Voronoi Voronoi Diagram algorithm, it is indeed a disguised Diagram in the Laguerre geometry. Apparently, it halfspace intersection algorithm, namely a dual ver- is also known as a Dirichlet cell complex IP]. sion of Preparata and Hong's convex hull algorithm IP-Hi. PS y (53 v V(1? V v F?gure 3.2 Note 3.3: We want to point out that VoDs as defined in example 3.3 model a seemingly natural growth process. Imagine a set of non-overlapping circular cells Ce in the plane, each increasing with time in such a way that the growth rate of its radius is inversely proportional to its diameter. Whenever two cells come into contact, they cease to grow in the directions in which overlap would occur. The eventual shape of each cell of such a growth system is given by a VoD as in Example 3.3, where the col- lection g consists of a function g for each cell C?, where Ps is the center of C5, and t5 is the time when it started growing, i.e., the last time when its radius would have been zero. This can easily be seen as follows: the growth rate of each cell C5 defines a real valued function g? telling for each point in the plane at what time it would be covered by C5 if it grew uninhibitedly. Foi each point in the plane one wants to know which cell(s) overgrow it first. Thus the Voronoi Diagram of the functions in g is indeed the desired object. Now it remains to show that the functions g? have the form given in example 3.3. We want the radius of an uninhibited circu- lar cell C, with center p? to grow at a rate inversely proportional to the diameter of C, star? ing at time t5. If r(t) denotes the radius changing with time, then it must satisfy the differential equa- tion dr __ I 7t --H 2r(t) with initial condition r(t5)=O. The solution to this equation is given by r(t) ff??t?t5, or r(t)2= t --Ht5. Expressing the radius r (t) in terms of Cartesian coordinates yields t = (z ?pt)TI(: p,) + 4 Example 3.4: For e E E let Pe again be a point in the plane, and let J be a 2>c2 diagonal matrix with entries 1 and 1. Let g? be the collection of functions g?, with = (z?pc)?J(z?pe). The way VOD(g1) partitions the plane is rather peculiar. It appears to be a mixture of a Euclidean closest point VoD in the z-direction and and Euclidean furthest point VoD in the y-direction. An example is given in Figure 3.2. To our knowledge this type of planar VoD has appeared in the literature only once, in a marginal remark in iliMi. It is unclear whether it has any applications. IV. Order-k and Degre?k Voronoi Diagrams Recall our definition of a VoD at the begin- ning of the previous section. We defined it via an equivalence relation Pi on a domain D with respect to a set I: of real valued functions on D, where p? was defined by S Pi I o+* where R1(r) --H e E E A(:)--Hmin!?(r) ). Obviously, there are ways of generalizing this definition by replacing the equivalence relation Pi by another one which is not based on the minimum of the function values, but rather on the k-th smal- lest. With this in mind we give the following definition of a k-minimum: Let E be an index set, and for i E E let : E R. For an integer k, k--Hmin z, is then defined to be the least real number such that z, _ for k elements i of E. We can now generalize the mapping R1 of section 3 in two interesting ways. For n integer k, l / ?? , C?(bJ,(a),tc)> ?c C - 2?Vfa) ? -- 2-V(b) 2?V(b,c) Figure 4.1: A degree-2 Voronoi Diagram C .a'MYi;YYffi)" syffiffiffi fa R 2?V?(b,c) 2-Wfa.b) Figure 4,2: An order?2 Voronoi Diagram It should be clear that both order- 1-VOD(f) and degree- 1-VOD(f) are the same as VOD(f1). In the Euclidean case (i.e. 1: is chosen as in E?am- pie 3.1) the degreek Voronoi Diagram partitions the plane by the kt nearest neighbor, whereas the order-k Voronoi Diagram partitions the plane by the k nearest neighbors. Both the order-k and the degree-k Voronoi Diagram appear to be fairly natural generalizations of the ordinary VoD. So it is somewhat surprising that except for a short remark in ?C-Y' so far only the order-k VoD has been considered in the compu- tational geometry literature Ish-Hl,fL761,IDl, [Bhaj.1 The main reason for this appears to be the fact that in the Euclidean case order-k V-regions are always convex and connected, whereas degreek V- regions generally consist of several convex com- ponents. As in the case of VOD(!), and perhaps even more so, it turns out to be beneficial to view degreek-VOD(f) and order-k-VOD(!) as derived from the f -arrangement in D x R. To this end we have the following theorems. Theorern 4.1: For e E E let fe be a real valued function on For some T C E let k-Vr be a degreek V-cell. k-Vr is the union of proj(C) over all k-level cells C in the f?-arrangement of the form c --H Proof: Let r E k--HVr and let r =k--Hminf,(:). By El definition we have f,(z)--Hr for e E T. Let = e f,(x) < r ). By the definition of the k-min it must be the case that lE-; < k, but ITI+ IE-I>k. But this is the case iff (x,r) E C<:?,r?+> where E+ = - and C<1mr?+> is a k-level cell. We state similar theorems for the order-k Voronoi Diagram. The proofs follow directly from the definition and are omitted. Theorem 4.2: For some T C E let k-Wr be an order-k V-cell. k--HWr is the union of proi(C) over all k-level cells C in the /-arrangement with c --H and r=E-uE0). Even more useful might be the following 1The reader may convince him?elf that our definition of order-k-VOD(!) actually agree' with the definitions offered in these papers. when J is chosen as in Example 3?1 of the previous section. Theorern 4.3: For some T C E let k--HWr be an order-k V-cell. If k- lVr is an order-k Voronoi region, then k--HWr --H proi(C) and C is a k-belt cell in the Is- arrangement. Otherwise k--HWr is the union proj(C) over all cells C that are k-level as well as (k+ 1)-level cells and that are of the form C --H with E-uE0--H T. Figures 4.1 and 4.2 illustrate the contents of the preceding theorems. The preceding theorems and Lemma 2.1 have an important corollary. Corollary 4.1: Let It and gg be two order-equivalent collections of functions on a common domain D. For I 1, and let It be a co? lection of n affine functions from Rd to R, or let fg be a set of n quadratic functions on Rd gen- erated by one common real symmetric matrix A as in Theorem 3.2. For l < k < n all degreek and order-k Voronoi Diagrams with respect to fz can be constructed in time and space 0(nd+l). This is worst case optimal. Proof: By the preceding results it suffices to construct all cells in the f5-arrangement. By Fact 2.2 (and in case of the quadratic functions because of Lemma 2.2) this can be done optimally in the given time and space bound. Q.E.D. The reader may again consult the examples in section 2 to see that this result covers a rather general class of Voronoi Diagrams, among them, of course, the ordinary Euclidean VoD of point sets. Our result should also be contrasted with the O(n? algorithm proposed in IDI to construct all Euclidean order-k VoDs of a planar point set. The optimality claim made there clearly has to be taken with a grain of salt. Finally there remains the question of how to construct single order-k or degreek VoDs for affine or quadratic function collections. As a consequence of the main theorems in this section this is equivalent to constructing all k-level or k-belt cells in an ?1-arrangement. Thus the time bounds stated in Fact 2.5 apply. However, they appear to be rather weak and we cannot make any claims about optimality. V. Intersection Problems In this section we want to show briefly how an f-arrangement can be a useful tool for solving certain intersection or union problems for finite sets of objects. Note that using de Morgan's laws, union can be reduced to intersection. We therefore res trict ourselves to intersection problems. At first we describe our method abstractly, later we apply it to solve intersection problems for finite sets of discs and, more generally, finite sets of similar conic sec- tions in R' For e E E let Be be some subset of our domain D and assume for each e there is a real- valued function fe on D with I' (:) < 0 iff : E B,. We are interested in describing fl Be in El terms of the /1.arrangement. For this purpose let us identify every subset B C D with its inlection ((x,O)j:EB) into DxR. This way we can write for every e E E that Be --H The intersection fl Be can then be written as ,El eY1(/e?flD) --H Dfl which is of course nothing but D n This means one can construct fl Be by first con- El structing the "top" full cell C<1,.,.> of the fl- arrangement and then intersecting this cell with the "base plane" ( (:,O) I: E D ). As an example consider the problem of con- structing the intersection of a finite set of open discs in the Euclidean plane R2, where each disc B, has center Ce E R2 and radius re >0. Associate with each disc Be the real-valued func- tion /? on R2, where for : E R2 (r ce)TJ(: cc) --H re2 and I is the identity matrix. Note that as desired the condition z E Be iff Je (x) <0 holds. Therefore the idea outlined above is applicable. First construct the cell C<1,n.> formed by the intersection of the upper hemispaces /e? As all the functions f? are quadratic functions generated by the same matrix I, the results of section 2 imply that ? can be constructed in O(nlogn) time. This cell can then be intersected with the base plane ( (:,O) z E R2) in 0(n) time to yield the intersection fl Be of all the discs in 0(nlogn) El time overall. The same approach can be used to construct the intersection of n open balls in Rd in time 0(n kd+i)/2l) for d > 2. This method of constructing the intersection of discs is very closely related to the one proposed by Brown ?B8o1. He uses spheres and spherical inversion to reduce the problem to one of intersec? ing halfspaces, whereas we, if one analyzes our method in detail, use paraboloids and the "warp- ing" function F1 given at the end of section 2. We briefly want to mention some more gen- eral applications of our method of using the Il- arrangement formalism to solve intersection pro? lems. One concerns intersecting regions Be of the form B, =(? ER' I!e(:)<0) where --H (z?cc)?A(z?cc) + r? Cc E Rd, r, E R and A a fixed nonsingular symmetric matrix. Such regions Bc are general conic sections. For instance, in the case d =2 and A indefinite, Be might be the unbounded (non-convex) region between the two branches of a hyperbola With our formalism the intersection of" such regions Be can be accom lished in 0(nlogn) time in case d =2, and 0(n d+1)/2l) time in case d>2. Note that Brown's method cannot be used for this purpose as it relies on spherical inversion. The machinery of J1-arrangements can also be used to solve intersection problems of the form "find all : that lie in exactly k regions Be." Find- ing such a set reduces to the problem of intersec? ing the k-belt cells of an fg-arrangement with the "base plane". Similarly, the boundary of the set of all x that lie in at least k regions Be can be con- structed via intersecting the k-level cells with the "base plane". We leave the details to the reader. v'. Conclusions The initial seed for the ideas in this paper was the observation that Voronoi Diagrarns of point sets in the plane are related to ?dimensional polyhedra whose facets are tangent to a common paraboloid. We discovered this while scrutinizing K.Q. Brown's use of spherical inversion to relate Voronoi Diagrams in the plane with ?dimensional polytopes whose vertices all lie on a common sphere [B7sJ.2 At first these relationships seemed rather mysterious and inexplicable. Only after we turned our attention to the question of what Voronoi Diagrams really are, did we arrive at the (we think) satisfying explanation of these relationships presented in this paper. An important concept in this paper is the notion of an 1:-arrangement over a domain D, i.e. the partition of D xR induced by a finite collection I: of real valued functions on D. Of course, in its full generality this concept is quite useless. How- ever, with appropriate restrictions I:-arrangements can provide for interesting geometric.combinatorial research. For instance, if D --H R4 and the func- tions in f are continuous and satisfy certain sim- ple finite intersection properties, 1:-arrangements have been studied fairly extensively as pae"dopLane arrangements [G71J,[G72j and also in the context of orsented matroida iMI. From the point of view of cornputational geometry, pseudoplane arrangements still offer some interesting algorithmic problems. How difficult is it, for instance, to construct all cells in such an arrangement when only I: is given? It seems that the 0( ? d + 1) algorithm in [EOSl actually generalizes to that case. How difficult is it to con- struct all k-level cells? In particular, for D --H R2 is it possible to construct the 1-level cells in O(n logn) time? This would yield a fast construc- tion algorithm for a large class of planar Voronoi Diagrams. Finally there is the question whether there are other interesting classes of j-arrangements. There appear to be several natural and promising ways of arriving at such arrangements. One would be to relax or change the finite intersection proper- ties of functions postulated in the case of pseudc- plane arrangements. For instance, in the case D --H R2, allowing two surfaces to intersect and cross either in a line or in a simple closed curve would give rise to a class of arrangements that includes the ones that correspond to weighted Vor? noi Diagrams [A-E]. Another interesting way of generalizing would be to change the underlying domain D to, say, a torus, and to try to postulate appropriate intersection properties for that case. Acknowledgements: We would like to thank John Gilbert ror his careful reading of the manuscript and his many suggestions for improvement. We also want to thank Bennett Battaile, Gianfranco Bilardi, Joseph O'Rourke, and Chee Yap for their comments. 2Actually it turns out that the use of paraboloid' and spheres to relate Vorono Diagrams and polyhedra are projectively equivalent References [Al Aurenhammer,F. "Power Diagrams: Proper- ties, Algorithms and Applications." fiG, Tech. Univ. Gras, Austria; Rep. F120; 1g83. [A-Bj Ash,F.P. and Boler,E.D. "Generalised Diri- chlet Tesselations." Nlanuscript; submitted to Geometriae Dedicat? [A-El Aurenhammer,F. and Edelsbrunner,H. "An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane." Pattern Recogn? tion, 17,2, pp.251-257; 1?84. [BhajBhattacharya,B. "An Algorithm for Compu? ing Order k Voronoi Diagrams in the Plane." Simon Fraser Univ., Burnaby B.C.; CS Dept. Tech. Rep. TR. 8??; 1S83. [BowJ Bowyer,A. "Computing Dirichlet Tessela tions." The Computer Journal 24; pp.162-166; 1g81. [B781 Brown,K.Q. "Fast Intersection of Half Spaces." Dept. of CS, CNW, Pittsburgh PA; Rep. CMU-C?78l2S; 1g78. [B??l Brown,K.Q. "Voronoi Diagrams from Convex Hulls." Information Processing Letters g; pp.22? 228; IO7?. [B80J Brown,K.Q. "Geometric Transforms for Fast Geometric Algorithms." Dept. of CS, CMI;, Pitta burgh PA; ph.D. Thesis; Rep. CMU-C?8o101; 1g80. [CDI Chew,L.P. and Drysdale,R.L.ffl "Voronoi Diagrams to Solve Largest Empty Oriented- Convex-Shape Problems." Dep. of Math. and CS; Dartmouth College, Hanover, NH; Extended Abstract; 1S84. [CYl Cole,R. and Yap,C.K. "Geometric Retrieval Problems." Proc. of the 24th IEEE Symp. on Foun- dations of Computer Science; pp.112-121; 1S83. [DI Dehne,F. "An Optimal Algorithm to Con- struct all Voronoi Diagrams for Ic Nearest Neighbor Searching in the Euclidean Plane." Proc. of the 20th Annual Ailerton Conf. on Communication, Control, and Computing; lS82. [Dryl Drysdale,R.L.ffl "Generalized Voronoi Diagrams and Geometric Searching." Stanford Univ., Stanford, CA, CS Dept.; Ph.D.Thesis, Rep. STAN-C?7S-705; 1s7g. [El Edelsbrunner,H. "Arrangements and Geometric Computations." Forthcoming book. [EOslEdelsbrunner,FL, O'Rourke,J. and Seidel R. "Constructing Arrangements of Lines and Hyper- planes with Applications." Proc. 24th Symp. on Foundations of Computer Science, pp.8?S1; lS83; (to appear in SlAM J. Computing). [EWl Edelsbrunner,H. and Welzl,E. "On the Number of Line?Separations of a Finite Set in the Plane." llG, Tech. Univ. Gras, Austria; Rep. F?7; 1082; (to appear in J. Combin. Theory, Ser. A). lELSSl Erdoes,P., Lovass,L., Simmons,k and Straus,E.G. "Dissection Graphs of Planar Point Set&" in A S"r?e; of Combinatorial TAeor;, J.N.Srivastava et al., eds.; NorthHolland, Amster- dam; 1273. 1G711 Grunbaum,B. "Mmngements and Hyper- planes." Conf.Numerantium ffl, Louisiana Conf. on Comb., Graph Theory and Computing; pp.41-lOS; 1271. 1G721 Grunbaum,B. "Arrangements and Spreads." Reg. Conf. Series in Math., AMS, Providence; 1272. [IIMJ Imai,H., Iri,M. and Murota K. "voronoi Diagrams in the Laguerre Geometry and its AppIi- cation." SlAM J. Computing; to appear. IKI Kirkpatrick,D.G. "Efficient Computation of Continuous Skeletons." Proc. of the 20th WEE Symp. on Foundations of Computer Science; pp.l827; 1272. [L7'sJLee,D.T. "On Finding h-Nearest Neighbors in the Plane." Univ. of Illinois, Urbana fli., Coordi- nated Science Lab.; M.S. Thesis, Rep. R-728; 1276. jL8OjLee,D.T. "Two Dimensional Voronoi Diagrams in the L,-metric." J.ACM, pp.6046l8; Oct. 1280. [L-Dj Lee,D.T. and Drysdale,R.S.ffl "Generalized Voronoi Diagrams in the Plane." SlAM J. Compu? ing, 10,1, pp.7387; Feb. 1281. [L-W?ee,D.T. and Wong C.K. "Voronoi Diagrams in Lu(Loo?) Metrics with 2-Dimensional Storage Applications." SlAM J. Computing; 2,1, pp.2(X? 2111280. [MM] McMullen,P. "The Maximum Number of Faces of a Convex Polytope." Mathematika 17; pp.172-1841270. [MJ Mandel,A. "Topology of Oriented Matroids." Univ. of Waterloo, Waterloo, Ont., Dept. of Com- binatorics and Optimization, ph.D. Thesis; 1281. IPi Paschinger,1. "Konvexe Polytope und Diri- chletsche Zellenkomplexe." Math.Inst., Univ. Salzburg, Austria; Arbeitsbericht 1-2; 1282. [P-H]Preparata,F.P. and Hong,S.J. "Convex Hulls of Finite Sets of Points in Two and Three Dimen- sions." C. ACM 20; pp.87-231S77. ?P-M?reparata,F.P. and Muller,D.E. "Finding the Intersection of n Halfspaces in Time O(nlogn)." Theoretical Computer Science 8; pp.45551272. 151 Seidel,R. "A Convex Hull Algorithm Optimal for Point Sets in Even " Dept. of CS, Univ. of BC, Vancouver B.C.; Rep. 81-14; 1281. 15h-Hlshamos,M.I. and Hocy D. "Closest-Point Problems." Proc. of the 17th WEE Symp. on Foundations of Computcr Science; pp.208-215; 1275. [?Lj Sharir,M. and Leven,D. "Intersection Prob- lems and Applications of Voronoi Diagrams." in Ad'ances tn Robotics, Vot. 1: Atgont?mic and Geometric Aspects of Robotics, cd. J.Schwartz and C.K.Yap, Lawrence Erlbaum Associates Inc. (to appear). (Wal Watson,D.F. "Computing the i-Dimensional Delaunay Triangulation with Applications to Vor? nol Polytopes." The Computer Journal 24; pp.l67-l72; 1281. [YapiYap,C.K. "An O(i logs) Algorithm for the Voronoi Diagram of a Set of Simple Curve Seg- ments." Courant Institute of Math. Sciences, NYU, New York, NY; Manuscript; 1284. Izi Zaslavsky,T. "Facing up to Arrangements: FaceCount Formulas for Partitions of Space by Hyperplanes." Memoirs AMS 154, Providence; 1g75.