Verification of partitions of 2d and 3d objects

Verification of Partitions of 2d and 3d Objects Leonidas Palios Department of Computer Science, University of Ioannina, 45110 Ioannina, Greece Abstract We consider the problems of deciding whether a given collection of polygons (polyhedra resp.) forms (i) a partition or (ii) a cell complex decomposition of a given polygon (polyhedron resp.). We describe simple O(nlog n)-time and O(n)-space algorithms for these problems, where nis the total description size of the input. If, in the input, vertices are referenced by means of indices to an array of distinct vertices, then our cell complex decomposition verification algorithms run in O(n) time. 1. Introduction In recent years, there has been growing interest in algorithms that enable us to check the output of a program. This issue has been considered from different viewpoints, and the research yielded results ranging from characterizations of problems that are checkable [2] to special-purpose checkers. In particular, in computational geometry, this issue proves to be crucial as the newer and more efficient algorithms are more and more complicated. Usually, the authors of an algorithm for computing some geometric object describe properties of the object which can be used to verify the correctness of the computation (see e.g. [1] and [4] for 2d and 3d triangulations of point sets). Often, however, more machinery is needed. The first verification algorithms (“checkers”) were provided by Mehlhorn et al. who defined the properties that a checker should have (correctness, simplicity, efficiency) and described checkers for convex polyhedra and convex hulls [5]; they have also studied checkers for trapezoidal decompositions, planar point location structures for trapezoidal decompositions, and Voronoi and Delaunay diagrams. Devillers et al. extended the notion of checkers and provided checkers for convex polytopes in two and higher dimensions, and for various types of planar subdivisions [3]. Their algorithms run in linear time, assuming that the input is a 2d or a 3d ordered geometric graph. Email address: [email protected] (Leonidas Palios). In this paper, we present simple and efficient verification algorithms for partitions and cell complex decompositions of simple polygons and polyhedra. The algorithms rely on appropriately matching the edges of the 2d decompositions and the facets of the 3d decompositions, and run in O(nlog n) time using O(n) space, where nis the total size of the input. If, in the input, vertices are referenced by means of indices to an array of distinct vertices, then our cell complex decomposition verification algorithms run in optimal O(n) time. Note: In the following, a polygon or a polyhedron is understood to be a simple one. 2. The Two-dimensional Case We assume that each polygon in the input is described by the sequence of its vertices along its boundary, where each vertex is given by its coordinates. 2.1. Verification of a partition of a polygon Lemma 1 Let Pand Cbe a polygon and a collection of polygons respectively. Additionally, let EI= {e−∂P |eis an edge of a polygon in C} and EB= {e∩∂P |eis an edge of a polygon in C}. Then, the collection Cforms a partition of Pif and only if (i) the set EIof (parts of) edges of the polygons in Ccan be partitioned into sets Sand S′such that •Ss∈Sclosure(s) = Ss∈S′closure(s), 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry •the closures of the segments in Sand S′define a partition of Ss∈Sclosure(s), and •for each (part of) edge ein S(resp. S′), if S′[e] (resp. S[e]) is the set of segments of S′(resp. S) that are collinear with and intersect e, then, locally around e, the interior of the polygon in Cwith edge eand the interiors of the polygons in Cwhose edges contributed the elements of S′[e](resp. S[e]) lie on opposite sides of the line supporting e; (ii) the closures of the segments in EBform a partition of the boundary ∂P of P, and for each (part of) edge ein EB, locally around e, the interior of the polygon in Cwith eas an edge and the interior of Plie on the same side with respect to the line supporting e. The partition verification algorithm applies Lemma 1. It uses an (initially empty) array A of size equal to the total number of edges of the polygons in Cand of the polygon P. 2d Partition Verification Algorithm 1. Orient the boundary of polygon Pand the boundaries of the polygons in Cin a compatible fashion (e.g., the boundary is traversed in a ccw fashion). 2. For each polygon Qin Cdo for each edge −→ uv of Qdo if uis lex-smaller than v then add the entry (u, v, +1) in A; else add the entry (v, u, −1) in A; 3. For each edge −→ uv of Pdo if uis lex-smaller than v then add the entry (u, v, −1) in A; else add the entry (v, u, +1) in A; 4. Sort the entries (ui, vi,±1) of the array Aby slope of the line uiviand, in case of ties, lexicographically taking into account the coordinates of the vertices uiand vi. 5. For each slope separately, traversethe related entries of Averifying that those with “+1” and those with “−1” partition the same set of segments. If this terminates successfully, then the collection Cof polygons defines a partition of the polygon P, otherwise it does not. Time complexity. Steps 1, 2, and 3 can be completed in time linear in the total description size n of the input, while Step 4 takes O(nlog n) time. Step 5 takes O(n) time: for each slope, the sorting of the entries implies that each new entry with “+1” either is the extension of the latest entry with “+1” or starts a new segment in the union of the “+1”-entries (if not, Cdoes not form a partition of P), and similarly for the “−1”-entries. The algorithm uses O(n) space. 2.2. Verification of a cell complex decomposition of a polygon Lemma 2 Let Pand Cbe a polygon and a collection of polygons respectively. Then, the collection C forms a cell complex decomposition of Pif and only if the set of edges of the polygons in Ccan be partitioned into two sets EIand EBsuch that (i) for each edge ein EIthere exists exactly one other edge, say d, in EIsuch that e=dand, locally around e, the interiors of the polygons in Cwith edges eand dlie on opposite sides of the line supporting e; (ii) the edges in EBform a partition of the boundary ∂P of Pand for each edge ein EB, locally around e, the interior of the polygon in Cwith edge eand the interior of Plie on the same side with respect to the line supporting e. The cell complex verification algorithm applies Lemma 2; it too uses an (initially empty) array A of size equal to the total number of edges of the polygons in C. 2d Cell Complex Verification Algorithm 1. Collect all the vertices and assign to each one of them a distinct positive integer id( ). 2. Orient the boundary of polygon Pand the boundaries of the polygons in Cin a compatible fashion. 3. For each polygon Qin Cdo for each edge −→ uv of Qdo if uis lex-smaller than v then add (id(u), id(v),+1) in A; else add (id(v), id(u),−1) in A; 4. Sort the array Alexicographically. 5. Traverse the sorted array Adeleting matching entries (i.e., (k, k′,−1) and (k, k′,+1)), which now appear next to each other. 6. Collect the unmatched entries and by applying a depth-first traversal construct the graph that these entries form. If this graph is a closed path identical to the boundary of the polygon P, then the collection Cof poly- March 25-26, 2004 Seville (Spain) gons defines a cell complex decomposition of P, otherwise it does not. Time complexity. If nis the total description size of the input, Step 1 can be executed in O(nlog n) time by means of a balanced binary search tree to determine identical vertices. Steps 2 and 3 take O(n) time; so does Step 4 (by using radix sorting), and Steps 5 and 6. Thus, the algorithm takes a total of O(nlog n) time. The space required by the algorithm is O(n). Observe that all the steps of the above algorithm but Step 1 take O(n) time. Moreover, if the input consists of the list Vof distinct vertices of the polygon Pand of the polygons in the collection C, followed by the vertices of each polygon, where each vertex is referenced by its index to the list V, then we do not need to execute Step 1. Such a representation is commonly used, and is easily produced by partitioning programs. Then, it can be determined whether the collection Cforms a cell complex decomposition of Pin O(n) time using O(n) space. 3. The Three-dimensional Case We assume that each polyhedron in the input is described by a list of its facets, each represented by the sequence of its vertices along its boundary, where each vertex is given by its coordinates. Our verification algorithms rely on two lemmata similar to Lemma 1 and Lemma 2. 3.1. Verification of a partition of a polyhedron Lemma 3 Let Pand Cbe a polyhedron and a collection of polyhedra respectively. Additionally, let FI={f−∂P |fis a facet of a polyhedron in C} and FB={f∩∂P |fis a facet of a polyhedron in C}. Then, the collection Cforms a partition of Pif and only if (i) the set FIof (parts of) facets of the polyhedra in Ccan be partitioned into two sets Sand S′such that the closures of the polygons in each of these sets defines a partition of Ss∈Sclosure(s), and for each (part of) facet fin S(S′resp.), the interior of the polyhedron of Cwith facet fand the interiors of the polyhedra of Cwith facets the polygons of S′(Sresp.) which intersect with flie (locally around f) on opposite sides of the plane supporting f; (ii) the closures of the polygons in FBform a partition of the boundary ∂P of P, and for each (part of) facet fin FB, locally around f, the interior of the polyhedron of Cwith facet fand the interior of Plie on the same side with respect to the plane supporting f. In light of Lemma 3, we have: 3d Partition Verification Algorithm 1. Orient the facets of the polyhedron Pand of the polyhedra in Cin a compatible fashion (i.e., in counterclockwise order as seen from outside the polyhedron). 2. For each polyhedron Qin Cdo for each facet fof Qdo u←the lex-smallest vertex of f; if f’s boundary forms a left turn at u then add the entry (f, +1) in A; else add the entry (f, −1) in A; 3. For each facet fof Pdo u←the lex-smallest vertex of f; if f’s boundary forms a left turn at u then add the entry (f, −1) in A; else add the entry (f, +1) in A; 4. Sort the entries (fi,±1) of the array Aby slope of the plane supporting fiand, in case of ties, lexicographically on the second field of the entry. 5. For each slope separately, verify that the related facet records with “+1” and those with “−1” partition the same polygonal regions. If this matching terminates successfully, then the collection Cdefines a partition of the polyhedron P, otherwise it does not. Time complexity. Steps 1, 2, and 3 can be completed in time linear in the total description size n of the input. Step 4 takes O(nlog n) time. Step 5 can also be completed in O(nlog n) time: for each different plane slope, collect the entries with “+1” as second field, and apply on the associated facets Steps 2 and 4 of the 2d partition verification algorithm (see Section 2.1); Step 5 of that algorithm is applied next, except that the difference of the union of the “+1” and the “−1” entries is computed and used to form a graph; the same procedure is applied to the entries of the array A with “−1” as second field; finally, the two resulting graphs are checked to see whether they are identi- 20th European Workshop on Computational Geometry cal. Thus, the algorithm takes a total of O(nlog n) time. The algorithm uses O(n) space. 3.2. Verification of a cell complex decomposition of a polyhedron Lemma 4 Let Pand Cbe a polyhedron and a collection of polyhedra respectively. Then, the collection Cforms a cell complex decomposition of Pif and only if the set of facets of the polyhedra in Ccan be partitioned into two sets FIand FBsuch that (i) for each facet fin FIthere exists exactly one other facet, say f′, in FIsuch that f=f′and, locally around f, the interiors of the polyhedra in Cwith edges fand f′lie on opposite sides of the plane supporting f; (ii) the edges in FBform a partition of the boundary ∂P of Pand for each facet fin FB, locally around f, the interior of the polyhedron of Cwith facet fand the interior of Plie on the same side with respect to the plane supporting f. The cell complex verification algorithm applies Lemma 4. It uses two auxiliary arrays Aand B, which are initially empty; it works as follows: 3d Cell Complex Verification Algorithm 1. Collect all the vertices and assign to each one of them a distinct positive integer id( ). 2. Orient the facets of the polyhedron Pand of the polyhedra in Cin a compatible fashion. 3. For each polyhedron Qin Cdo for each facet fof Qdo a←the lex-smallest vertex of f; b←the lex-largest vertex of f; c←f’s vertex farthest away from the line ab (and lex-smallest, if ties); if f’s boundary is directed a c b then add ((id(a), id(b), id(c)),+1) in A; else add ((id(a), id(b), id(c)),−1) in A; 4. Sort the array Alexicographically. 5. Traverse the sorted array A, verify that matched entries (which now appear next to each other) correspond to matching facets and delete them. 6. For each facet fwhose entry in Ahas not been matched do for each edge −→ uv of fdo if uis lex-smaller than v then add (id(u), id(v),+1, f) in B; else add (id(v), id(u),−1, f) in B; 7. Sort the array Blexicographically. 8. If the entries in Bdo not appear in matching pairs (i.e., (k, k′,−1, f) and (k, k′,+1, f′)), then the collection Cof polyhedra does not define a cell complex decomposition of the given polyhedron P. 9. For each matching pair (id(u), id(v),−1, f) and (id(u), id(v),+1, f′) in Bdo if the two facets f, f′are not coplanar then make uand vadjacent; 10. Apply a depth-first traversal and check that the graph formed matches the edge skeleton of the polyhedron P. If it does, then the collection Cof polyhedra defines a cell complex decomposition of P, otherwise it does not. Time complexity. Step 1 takes O(nlog n) time, as described in Section 2.2. Steps 2, 3, 5, and 6 take O(n) time. Steps 4 and 7 can be completed in linear time as well by using radix sorting. Finally, Steps 8, 9, and 10 also take linear time. Thus, the algorithm requires a total of O(nlog n) time. The space required by the algorithm is O(n). Similarly to the two-dimensional case, if the polyhedron Pand the polyhedra in the collection C are represented by a list of facets, each described by a sequence of indices to an array of distinct vertices which indicates the order of the vertices around the boundary of the facet, then it can be determined whether the collection Cforms a cell complex decomposition of Pin time and space linear in the total description size of Pand C. References [1] D. Avis and H. El Gindy, Triangulating point sets in space, Discrete and Computational Geometry 2, 99– 111, 1987. [2] M. Blum and S. Kannan, Designing programs that check their work, Journal ACM 42(1), 269–291, 1995. [3] O. Devillers, G. Liotta, F.P. Preparata, and R. Tamassia, Checking the convexity of polytopes and the planarity of subdivisions, Computational Geometry: Theory and Applications 11(3-4), 187–208, 1998. [4] H. Edelsbrunner, F. Preparata, and D. West, Tetrahedralizing point sets in 3 dimensions, Journal of Symbolic Computation,10, 335–347, 1990. [5] K. Mehlhorn, S. N¨aher, T. Schilz, S. Schirra, M. Seel, R. Seidel, and C. Uhrig, Checking geometric programs or Verification of geometric structures, Proc. 12th Symp. on Computational Geometry, 159–165, 1996.