OPTIMAL ALGORITHMS FOR SYMMETRY DETECTION IN TWO AND THREE DIMENSIONS Jan D. Wolter Tony C. Woo Richard A. Volz Department of Electrical Engineering and Computer Science Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 February 1985 Technical Report 85-6

Optimal Algorithms for Symmetry Detection in Two and Three Dimensions* Jan D. Woltert Tony C. Woott Richard A. Volzt tDepartment of Electrical Engineering and Computer Science ttDepartment of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan U.S.A. 48109 *Work on this paper was partially supported by the Air Force Office of Scientific Research under contract number F4920-82-C-0089. Work by the first author was supported through an IBM Graduate Pre-Doctoral Fellowship.

2 Abstract: Exact algorithms for detecting all rotational and involutional symmetries in point sets, polygons and polyhedra are described. The time complexities of the algorithms are shown to be e(n) for polygons and 9(n logn ) for twoand three-dimensional point sets. 9(n logn) time is also required for general polyhedra, but for polyhedra with planar, connected surface graphs e(n ) time can be achieved. All algorithms are optimal in time complexity, within constants. Key words: Symmetry, Similarity, Computational Geometry, Pattern Matching, Graph Isomorphism. Introduction An object is symmetrical if its shape is unchanged under an affine transform. This paper presents optimal algorithms to find several types of symmetry for polygons, point sets, and polyhedra -- point, line and plane symmetries. The authors originally encountered the need for computing symmetry in a robotics application, in which a set of images of polyhedra were generated for the training of a vision system (Wolter et al., 1985). Knowledge of the symmetry of the object was necessary to eliminate redundant orientations. Because of its potential capability in data extraction and data compaction, the notion of symmetry is useful in solving problems in image analysis and computer graphics. Several algorithms for detecting symmetry in images have appeared in the literature. Davis (1977) described a method for finding lines of symmetry in images by clustering local symmetries. Parvi and Dutta Majumder (1983) detected approximate lines of symmetry in chain coded polygons. Friedberg and Brown (1984) used moments to find lines of skewed symmetry. Johansen et al. (1984) have presented algorithms based on the boundary representations of objects which may be used to detect symmetries. They extend an algorithm by Tanimoto

3 (1981) to encode polygons or polyhedra into nondeterministic finite state automata. This requires O(n2) states for polyhedra, and 0(2 " ) states for polyhedra, where n is the number of vertices. This paper presents a set of algorithms for solving the following class of problems. Given either a point set or a boundary representation of a polygon or polyhedron, all rotational and involutional symmetries are found. For polygons and polyhedra with planar, connected surface graphs, e(n ) operations are used. For all other structures, ((nlogn) operations are required. All algorithms are shown to be optimal within a constant. These algorithms are based on the linear time polygon similarity algorithm published by Manachar (Manachar 1978; Akl 1978; Bykat 1979) and on the linear time graph isomorphism algorithm by Hopcroft and Wong (1974). The computational model used throughout this paper is a RAM-based algebraic decision tree (Lee and Preparta, 1984). Definitions In this paper a d-dimensional object I is defined as a set of points {Pl, P2, } in d-dimensional space. The transform of an object T(I) is the object {T(pl), T(p2),... }. n is symmetric under the transform T, if r(n) = n. The transforms of interest in this paper fall in two classes: rotational transforms and involutional transforms. Let R4,, denote a rotation transform of 0 degrees about the (d-2)-dimensional axis a. All possible rotational symmetry transforms can be written as C4, Ra,360/k where k is a natural number. If n

4 is symmetric under C,k then a is called a "k-fold point of rotational symmetry" in two dimensions, or a "k-fold line of rotational symmetry" in three dimensions. Note that the transform Ca, is the identity transform. A one-fold axis of symmetry is called a trivial axis, since every object HI has such a symmetry. The second class of transforms are involutional transforms, denoted Zb,k where b is a (d-l)-dimensional axis, and k is a natural number. In two dimensions, only Zb,l is defined. This denotes a reflection through the line b. If a two-dimensional point set is symmetric under Zb,1, then b is called a "line of reflectional symmetry". In three dimensions, let b be a plane, and let b be a line perpendicular to b. Then the transform Zb,k is a rotation of 360/k degrees around the line b followed by a reflection through the plane b. If a H is symmetric under Zb k, then a line b is said to be a "k-fold line of involutional symmetry". Zbl and Zb, are of particular interest. Zb,l is pure reflection through the plane b, and if n is symmetric under that transform, b is said to be a "plane of reflective symmetry". Note that Zb,l is self inverse. Zb,2 is equivalent to inversion through the point where b intersects 6. We call such points "points of inversional symmetry". Any transform R, k or Zb k leaves at least one point fixed in space. If an object is symmetric under a transform, it can be shown that the centroid - of the object must be a fixed point under that transform. Since the centroid can be calculated in linear time, it is a very convenient starting point from which to search

5 for symmetries A rotational transform Ra e can be expressed as a composite of two reflectional transforms, Zb,l~ Z 1, such that b and c intersect at a to form an angle of 0/ 2 degrees. Because of this, any object with more than one reflectional symmetry must also be rotationally symmetric. The symmetries which may occur together form symmetry groups. All possible symmetry groups for two and three dimensions have been formally classified (Martin 1982; Lockwood and Macmillan 1978). Basic Ideas The algorithms in this paper will all follow the same general outline, which consists of three steps: (1) ORDER: Sort the points of the object into cycles. (2) ENCODE: Encode each cycle into a string of symbols. (3) CHECK: Test the symmetry of the encoded string. Before describing the specific algorithms in detail, we will define the structures produced by the ORDER and ENCODE steps. In these definitions, T is the set of all symmetry transforms to be tested for. The ORDER step takes the vertex set P C H1, and forms it into a cycle r = <c0, cl,..., c_->, where each c, is one of the n elements of P. This ordering is a cycle if it has the property that if II is symmetric under any transform T E T such that T(ci) = ci then for all k, T(c,+k) = Cj+k (Note that in this paper, all additions and subtractions in subscripts are assumed to be

6 done with the appropriate modulus, in this case, n ). The ENCODE step converts a cycle r into a finite string S on an infinite alphabet. Each element ci in the cycle will be encoded into an m-tuple of symbols s; such that for any transform T E T under which P is symmetric, if T(c,) = ci then s; = si. Furthermore, the string should be such that two objects 11, and H2 have encodings which are cyclic permutations of each other if and only if for some T E T, T(nI) = I2. In other words, it must contain enough information about the original object H1 to allow the construction of an object I2 which is equivalent to HI under some transform in T. The CHECK step makes use of the properties of the encoded string to locate all transforms in T which are symmetries for the object. This includes several different tests for different kinds of symmetry, but all are variations of the rotational similarity test of Manachar. His algorithm is as follows: Algorithm 0: Similarity of Cycles Problem 0: Given two encoded cycles, S and T, check if S is a cyclic permutation of T, i.e. if there is any k such that <8k, sk+, * * *, Sk+n-1> = <t0, t 1 * *, tn -l> To solve this problem, a substring pattern matching algorithm such as that of Knuth, Morris, and Pratt (1977) is used. Given two strings of total length m on a possibly infinite alphabet, the Knuth algorithm finds the first occurrence of one in the other in e(m ) time.

7 Algorithm 0 then consists of two main steps. First, we construct the following two strings A and B from the encoded cycles S and T. A = <s0, sl,, sn-i> B = <t0, tl,..., t -l to, t,..., tn 2> Second, we use the string pattern matching algorithm to determine whether A is a substring of B. If it is, then S is a cyclic permutation of T. Algorithm 1: Symmetry of a Polygon. Problem 1: Given a planar polygon, find all rotational and reflectional transforms under which it is symmetric. A polygon is represented by a sequence of n points (vertices) P = <Po, P, P-l>I and n line segments (edges) E = <eoi, e12,..., -e,,1> such that the edge e;,+1 has endpoints p, and p; +1. This representation is unique up to a cyclic permutation of E and P. Polygon ORDER Theorem 1.1: Cycle Property of Polygons. The vertex list P of a polygon is a cycle for rotation transforms. [Proof] Since an edge connects p, and pi+,, and the polygon is symmetric under the transform T there must be an edge connecting pi = T(p;) and T(p;+,). Thus T(p;i+) equals either pi+l or pi-l. The latter case can be excluded, because the vorticity of the triangle (-, pi, p;+l) would be opposite that of (T(i), T(p,), T(p;+l)), and this is impossible if T is a rotation transform. Thus we have that T(pi+l) = pyil, which by induction implies that

8 T (pi+) = Pi+k so P satisfies the cycle condition. | Due to theorem 1.1, the ORDER step of the algorithm is unnecessary for a polygon, since the vertex list P already forms a valid cycle. Polygon ENCODE The ENCODE step generates a two-tuple of measures for each point which describes the location of that vertex. For a measure to be a candidate for inclusion in the encoding, it should be invariant under rotation. These are measures of the location of the point relative to the centroid or relative to adjacent points of the polygon. Possibilities include: Ml) Distances between adjacent vertices. M2) Distances of vertices from the centroid. M3) Angles formed by edges at each vertex. M4) Angles formed at the centroid by two adjacent vertices. In his polygon similarity algorithm, Bykat (1979) uses measures Ml and M2. However, these do not yield a unique encoding. Figure la shows a polygon with vertices a, a2, a3, b, b2, c, c2 and c3, such that centroid(a 1, a 2, a3) = centroid(b 1, b 2) = centroid(c, c 2, c 3) = Figure lb is the same polygon but with the coordinates of points cl, c2 and C3 reflected through the line (b l,b ). Both figures have the same centroid, the same edge lengths, and corresponding points are the same distance from the centroid, yet the polygons are not similar.

A 2 a2 cI C3 1/, \ C /b2 \ l & b'. 01 2 II( C, I cla3 41(a (a) (b) Figure 1. Non-Uniqueness of length-radius encoding for polygons

9 Manachar encodes each vertex of the polygon cycle into a two-tuple containing measures Ml and M3. Thus s, = <dist(p,,p+il), angle(p;-l, Pi, Pi+l)> This plainly satisfies both the requirement that vertices which can be mapped into each other by a symmetry transform have the same encoding, and the requirement that the polygon be completely described by the encoded string. Constructing the string S = <s i, 2,..., sn-l> takes only linear time. An encoding using M2 and M4 is very convenient if the polygon is specified in polar coordinates about the centroid. This case will arise as part of the point set symmetry algorithm. Polygon CHECK To check for the rotational symmetry of a polygon, we need only to make a slight modification to algorithm 0. Let S be the encoded cycle of the polygon. We search for A = <s8, s1,.., n-l> in the string B = <8,.., sn-l, 81 8 * * *, 8,-l> If A first occurs in B' at offset k-l then the polygon must have n/k-fold rotational symmetry. At least a one-fold symmetry will be found for any polygon, since, if A is found nowhere else in B', it will be found at offset n-1.,Having found the rotational symmetries of the polygons, we now test for the reflectional symmetries.

10 Theorem 1.2: Reflection and Rotation in Polygons: Let P be a polygon with centroid -, and b be an arbitrary line containing -. Then there exists an angle of rotation 0 such that R,e Zb j(P) = P if and only if P has a some line of symmetry c. [Proofl If the polygon is symmetric under the reflection transform Zc 1 then P = Z,,1(P). Any arbitrary reflection transform Zb 1 is self-inverse. So P = Z,, Zb,1' Zb,(P). Suppose b and c intersect at a forming an angle 0/ 2. Then, their composition is R.,1. Then P = R,' Zb,l(P). On the other hand, if the polygon has no line of symmetry, the reversal of the above argument leads to a contradiction. | Using this theorem, we can test for lines of symmetry by reflecting one copy of the polygon about any line b containing the centroid and then using algorithm 0 to see if it can be rotated onto the original polygon. The reflection of the polygon can be found simply by taking the vertices in the order opposite to that given in P. It would be possible to repeat the ENCODE step for the reversed polygon, but it is more efficient to construct it directly from the forward encoded cycle. For example, if the encoding is based on measures Ml and M3 then the reversed encoding R of S would have terms

11 ri = <dist(p,_i,p,_-i-), angle( p,,1, P,_, n,-i-l)> Thus R can be found simply by rearranging the terms of the encoding S described above. Since we know that the polygon has k-fold rotational symmetry, the CHECK algorithm for reflectional symmetry can be improved by looking at only k symbols in the string. The test is then to use algorithm 0 to find if string S' = <So, S,.., -1 i> is cyclically similar to R = <r0, rl,...,.r-l> If a match between these strings is found index j, and k -j is odd, then there is a line of symmetry bisecting the angle at p(k-,yi1)/. If k-j is even, it bisects the edge connecting P(k — 2)/2 and P(k-j)/2' The k-1 other lines intersect the first line at the centroid, forming angles of 360/k degrees. Thus, reflectional symmetry can be found in 6(k) operations after 6(n ) processing to find the rotational symmetry. Algorithm 2a: Symmetry of a 2D Point Set Problem 2a: Given a finite two-dimensional point set, find all rotations and reflections under which that point set is symmetrical. A d-dimensional point set (d > 0) is any set of n points P = {Po, Pi., Pn-I} in d-dimensional space. No ordering of the points is assumed. Theorem 2.1: Complexity of Point Set Symmetry Testing: To find the symmetries of a d -dimensional point set n(n logn ) operations are required.

12 [Proof] Consider a one-dimensional point set whose centroid lies at the origin (Figure 2a). To test for reflectional symmetry through the origin, we must determine if the set of absolute values of the coordinates of points on the negative axis is equivalent to the set of coordinates of points on the positive axis. This is a set equivalence problem. Suppose there are n/ 2 points in each set. To verify that two sets are equivalent, it is necessary to find which of the (n/ 2)! permutations of the first set forms the second. The decision tree for this problem is identical to that for comparison sorting (Aho et al., 1974), so, as in comparison sorting, O(nlogn) time is required. The one-dimensional case is a special case of all higher dimensional problems, so this lower bound applies in all dimensions. | We will now develop an algorithm to find the symmetries of a twodimensional point set in e(n logn ) time. It will be based on the same three steps used in the polygon algorithm. Point Set ORDER In the polygon problem the cycle of points was given. For point sets it must be computed. Suppose the points are sorted by their polar coordinates around the centroid, taking the angle as the primary sort key and omitting any points at the centroid. This gives rise to a star-shaped polygon in which the points are connected in clockwise order around the centroid. If the point set is rotated this order will be preserved, since each point is rotated by the same angle. Thus, a rotation which superimposes point i on point j is a symmetry transform only if it also superimposes point i+k mod n on point j+k mod n, for all k. Therefore, this ordering of the points qualifies as a cycle. Since the algorithm requires

g<o * * —*-* -* * * ** * — (a) (b) Figure 2. Complexity of Symmetry Dectection

13 sorting, its complexity is e(n logn ). In practice, this algorithm may have a serious problem. Figure 3a shows a two-dimensional point set with the vertices sorted properly. But a very small error in the location of point a or point b may give rise to the cycle shown in figure 3b, which is not symmetrical. This behaviour makes the algorithm very sensitive to round-off errors. The problem of finding approximate symmetries in point sets is beyond the scope of this paper. However, we will describe a modification to the algorithm which makes it more robust in cases where the errors are much smaller than the distances between points, as for round-off errors. First, all points whose radii are equal within some c are formed into cycles, and then each cycle is sorted by angle. This gives rise to a set of cycles {l, 2,,..., m } instead of a single cycle (figure 3c). This modified algorithm is e(n logn ). Point Set ENCODE The algorithm to encode the cycles is essentially the same as in the polygon problem. Each point is represented by the difference between the polar angle coordinates of the point and its successor. The radii of the points need not be included, since they are constant within each cycle. Of course, other encodings could be used. Point Set CHECK'The tests to check a cycle for rotational and reflectional symmetry are exactly the same as those for polygons. We must, however, apply the tests to all

(a) (b) (c) Figure 3. Effect of errors on point-set ORDER algorithm

14 cycles of the point set. Let cycle r, have oi-fold rotational symmetry. The degree of symmetry for the total point set is the greatest common divisor of the orders of the rings, k =GCD(o 1, 0 2, ~ ~ ~, ). Theorem 2.2: Complexity of GCD-. Finding GCD(o 1, o,.., ~ ) requires only linear time. [Proof] To find GCD(a,b) requires 9(log max(a,b )) time (Aho et al. 1971; Knuth 1981), and GCD(a,b ) < min(a,b ). Thus the total complexity is of order less than or equal to m i log max(o;,min(o,, o;-_)) i-=2 since logz < x, this is less than or equal to: m Z max(o;, min(o 1,., oi -)) =2 Let mn be min(ol,... oi). Then m =o o and o; o if max(o,, nm;l) mi-_ =i - m-i_1 if max(oi, mil) = o Thus m; for i >2 is always the value not taken by max(o,, m,_l). Therefore every o, appears in the sum exactly once except mm, and the previous sum is equal to m V o, - min(o1.. om). i-l This is less than or equal to n, since each o, is less than equal to the number of points in cycle FI and each point is in only one cycle. Thus finding GCD(ol1, o2..., ~m ) requires O(n) operations. From the case in which there

15 is only one point in each cycle, it can be seen that this is, in fact, e(n). Thus the rotational symmetry can still be found in 6(n ) time, even when there:ire multiple cycles. Having done this, we can check the reflectional symmetry of each cycle. If all have lines of symmetry which are colinear, then the point set has that line of symmetry. This can be done in linear time, given that we know the rotational symmetry of the point set and thus need consider only one line per cycle. Thus, in two dimensions, all symmetries of a point set can be found in E(n logn ) operations. (Only the ORDER step actually requires e(n logn ) operations. The other steps are linear.) This is optimal, by theorem 2.1. Algorithm 2b: Axial Symmetry of a 3D Point Set Problem 2b: Given an axis and a three-dimensional point set, find the rotational symmetry of the polyhedron about that axis, and find all planes of reflectional symmetry containing that axis. In this section, only a the symmetries about a given axis are tested. The problem of proposing lines of symmetry will be considered in a later section. All three steps for this algorithm are direct extensions of the twodimensional ones. In the ORDER step, we first specify the points in a cylindrical coordinate system whose origin is at the centroid, and whose z-axis is parallel to the axis of rotation. We can then sort the points by their coordinates -- first partitioning points whose radii and z-coordinates fall within some c of each other into cycles, and then sorting each cycle by the angle. This requires e(nlogn)

16 operations. To ENCODE a cycle, each point can be represented by the difference between its cylindrical angle coordinate and that of the succeeding point in the cycle. The other two coordinates are already guaranteed to be equal within e for all points in a cycle. This requires ((n ) operations. Finally, the CHECK step is exactly the same as the two-dimensional case, so the total complexity of the algorithm to find all two-dimensional symmetries of a three-dimensional point set is e(n logn ). Algorithm 3a: Axial Symmetry of a Polyhedron. Problem 3a: Given an axis and a polyhedron, find the rotational symmetry of the polyhedron about that axis, and find all planes of reflectional symmetry containing that axis. A general polyhedron is a set of polygon sets (faces) in three-dimensional space such that an edge (pi, pi) occurs at most once among all the faces, and if it does occur then (pi, pi) is also an edge of exactly one face. This definition forces the surface to be oriented and closed, but does not rule out selfintersections or disconnected surfaces. Theorem 3.1: Complexity of Polyhedron Symmetry Testing: For general polyhedra problem 3a requires at least 2(n logn ) operations. [Proof] Suppose problem 3a could be solved in less than (n logn ) operations. Given a one-dimensional point set (as in figure 2a), we could, in linear time, construct a polyhedron (figure 2b) with the same symmetries as the point set. Thus,

17 if there were a solution for problem 3a which took less than 0 (n logn ) operations, problem 2a could also be solved faster than O(n logn), This contradicts theorem 2.1, thus f2(n logn ) is the lower bound on problem 3a. I The implication of theorem 3.1 is that, for general polyhedra, no ORDER algorithm can be written that is better than the one described for 3D point sets. However, if we restrict our attention to polyhedra whose surface graphs are connected (Harary 1969), then the ORDER step can be preformed in linear time. Polyhedron ORDER We begin with the observation that a non-trivial line of symmetry can intersect the surface of a polyhedron in only one of three ways. It may intersect a vertex, the midpoint of an edge or the centroid of a face. In each case the points topologically adjacent to the point of intersection must be symmetric about the axis. These vertices will be used to form a cycle Fl. If the intersection point is on a face or a vertex, the ordering of the vertices in the cycle can be taken from the clockwise list of adjacent vertices. If the intersection point is on an edge, then there are only two adjacent points, so either ordering will do. If we define the vertices in rl to be at graphical distance one from the point of intersection, then all vertices p, rl1 which are connected by an edge to a vertex Pi E FI are a distance two from the point of intersection, and will form the cycle r2. Similarly the set of points whose distance in the surface graph from the intersection point is k (i.e. those that are connected by edges to points at distance k-l but not to points at distance less than k-l) must also be symmetrical

18 about the axis and will be placed in cycle rF. The ordering of rl is known and the ordering of each subsequent cycle can be deduced from the previous cycle. Each point in rk + is, by definition, edgeconnected to some point in rk. These edges define a many-tomany mapping between the points of the cycles. We use geometrical information to distinguish one of these edges for each point in rk +1. To do this, define a function A(py, pi ) whose value is the three-tuple of Cartesian coordinates of the point p, in the coordinate system whose origin is at pi, whose z -axis is directed parallel to the axis of rotation, and whose y-axis intersects the axis of rotation. This value is unique for all edges adjacent to pi, and symmetric points have exactly the same set of values for their adjacent points. Thus, for each point pi in rk +1 we distinguish the adjacent point Pi in rk which has the lexicographical minimum value for A(pi, pi ). This defines a mapping under which each point in rk+l maps into exactly one point in r,. The points in rk+l are placed in the same order as the corresponding points on rk, with those that map to the same point in rk placed in their clockwise order about that point. Let P = {Pi, P2,.., P.-I} be the vertex set of the polyhedron. Suppose that succ (i,j), the index of the clockwise successor of point pi around point pi, and pred (i, j ), the counterclockwise successor of point pi around p;, be computable in constant time. Then cycles of symmetric points about the given axis can be cpnstructed by the following algorithm. This algorithm constructs the m

19 cycles F1, 2,..., rm in the correct order in e(n ) time. ALGORITHM ORDER 3a: Construction of cycles from connected Polyhedron. initialize array cycle[0:n-l]:= UNSEEN. initialize array back[0:n - 1]. initialize linked lists rl:, empty. for each Pi which lies on the axis, cycle[i]: ONAXIS. Locate any intersection between the axis and the polyhedral surface. If the intersection is a vertex p,, for each pi adjacent to p, in clockwise order, append pi to rl. cycle[j]:= 1, back[j:= i. If the intersection is the midpoint of an edge (p,,p ), append Pi to rl. cycle[i]:= 1, back[i]: j. append pi to rl. cycle[j]:= 1, back[j]:= i. If the intersection is a face, for each edge (Pi,Pi) in clockwise order about the face, append pi to rl. cycle[j]:= 1, back[jl:= i. k:= 1 loop 1: while rk is not empty, loop 2: for each point pi in r,, j:= succ(i, back[i]). loop 3: while j 3M back[iJ step 3a: if cycle[j] = UNSEEN, append pi to rk +. cycle[j]:=k+1. back[j]:= i. step 3b: else if cycle[j] = k +1 and (pi, P backljl) > A(Pi, Pi) delete pi from rIk + append pi to rk+l. back[j]:= i. j:=succ(i, j). k:- k + 1. m: k - 1.

20 The following lemmas and theorems lead to a proof that the cycle construction algorithm is linear in complexity and correct. Lemma 3.2: During the execution of algorithm ORDER 3a, no vertex ever appears in two cycles or more than once in a cycle. [Proof] In each place where a vertex is added to any Fr, it is first verified that the vertex was marked UNSEEN before the insertion, and afterwards the UNSEEN mark is removed. The exception to this is step 3b, which only moves the vertex to the end of the list. Thus each vertex is only inserted once. | Theorem 3.3: Complexity of ORDER algorithm: The complexity of algorithm ORDER 3a is linear in the total number of edges E and the total number of vertices V. [Proof] Finding a point where the axis of rotation intersects the surface is accomplished by checking each face, edge, and vertex. The edge and vertex checks each require constant time. The face check is linear in the number of vertices bounding the face, which when totaled over the polyhedron, add to 2E. The initialization of rl requires fewer than V computations. Loop 2 iterates at most once per vertex. If the algorithm ever iterates on a vertex in r,, that vertex will still be in Fi when the algorithm terminates, because that iteration and all subsequent iterations operate only on Fi with j >i. Thus, if loop 2 iterated more than once on the same vertex, that vertex would appear more' than once among the final'r's. But Lemma 3.2 shows this to be impossible. The inner loop, loop 3, then iterates at most once per edge adjacent to each

21 vertex, or, in other words, twice on each edge. Thus, the algorithm is linear on V and E. I Theorem 3.4: Correctness of ORDER algorithm: All Fi constructed by the polyhedron ORDER algorithm are cycles. [Proof] Let rk = <k,0, l,1, -. ckn > and let the point's respective backpointers as given by back[] be <bko, bk,l,... bk,nk >. It is easily shown that rl is a cycle in all three cases. It is also easily shown that, if the polyhedron is symmetric under the rotational transform C and C(cl,;)= cl, then C(b1,I) =bl,j. We need to show that if rL is a cycle then the rk+1 as constructed by the polyhedron ORDER algorithm is also a cycle. We assume further that, if the polyhedron is symmetric under C and C(c,i ) = Ck, then C(b^,i ) = bk. Let Kk, be the list of vertices adjacent to k,i begining with bk,. These are the points inspected by loop 3. From the above, we can conclude that if C(ck,) = ck,j then C(Kk,) = Kki. Not all points in Kk, are actually inserted in Fk + by loop 3. Points in some rh where h < k are not included. Points which adjoin a previous point in r k+ for which the A function is larger are not included. Points which adjoin a subsequent point in rk + for which the A function is smaller are removed. Let Lk,i be the points of K,i which are actually inserted, namely those points Ph at distance k +1 from the intersection point for whom A(p,ck,) is equal to min(A(pa,c l,) for 0<l nk. Thus, the function A is defined to be invariant under C, if C(Kk,i)=- 1i, then

22 C(Lk,i) = Lk,i and Since if C(c^k,) = ck, then C (Lk, ) = L,, the concatination r+l = Lk,0 + Lk,l + * * + Lk,m must satisfy the cycle condition if,k does. Furthermore, the back-pointers for the points in Lk, point to Ck,, so if C(ck +,i)= ck +l, then C(bk+l,i ) = bk +,i This completes the induction step, and proves the theorem. | Polyhedron ENCODE The coordinates of the points can be encoded in a manner similar to that used for point sets. Each point is represented by a three-tuple composed of its cylindrical angle coordinate, the radius coordinate, and the z coordinate. In this case the second two coordinates must be included, because they may differ among points in the same cycle. In addition, each tuple must contain a list of points which are connected to it by edges of the polyhedron. The adjacent points should be given strictly in clockwise order, so that the locations of the faces can be deduced. They are each represented by the three-tuple A(p,, pi). The lists of points are rotated so the point back[i] is given first in each list. This ensures that the list of points is the same for all similar vertices. This encoding can be done in e(n ) operations. Polyhedron CHECK. The encodings produced by the previous step use tuples of variable size size to represent different points. To show that it is still possible to run the check

23 algorithms in linear time, we construct a new string from the original and show that it is linear in length. Let v;i, vi,2,,.., v,,, be the elements of the ith tuple. Let M be a value different from any v, y. Consider the string <M, v lI... Ivl,, n, M, v 2,1, - ~ ~, v2, ~ -, M, v,,, V.,n. > This has the same symmetry as the original string. For each vertex, it contains one M and three point coordinates. For each edge, it contains two three-tuples, one associated with the vertex on each end. Thus the total length is 4V+2E, which is e(n). We can thus conclude that the CHECK algorithm is still operates in ((n ) time. Algorithm 3b: Symmetry of a Polyhedron Problem 3b: Given a polyhedron, whose surface graph is connected and planar, find all involutional and roational symmetries. So far, we have considered only symmetry about a given axis. In this section we will show that all symmetries can be found in linear time. First the problem of finding all lines of rotational symmetry will be considered, followed by the problem of finding all planes of involutional symmetry. The possible arrangements of non-trivial lines of symmetry in threedimensional space are fairly restricted. These are designated as follows: (k) One k-fold line of symmetry, as in a regular k-sided regular cone. (2,2,k) One k-fold line of symmetry and k 2-fold lines of symmetry uniformly spaced in the plane perpendicular to the first line, as in a ksided regular prism.

24 (2,3,3) Four 3-fold lines and three 2-fold lines, arranged as in a regular tetrahedron. (2,3,4) Three 4-fold lines, four 3-fold lines and six 2-fold lines, as in a regular octahedron or hexahedron. (2,3,5) Six 5-fold lines, ten 3-fold lines and fifteen 2-fold lines, as in a regular dodecahedron or icosahedron. For a proof that this list is complete see Lockwood and Macmillan (1978) or Martin (1984). For polyhedra whose surface graphs are planar, it is possible to find the symmetry group of the surface graph in linear time by making use of the graph isomorphism algorithm of Hopcroft and Wong (1974). This algorithm finds all isomorphisms between two planar graphs by reducing each graph to either a ring, a skein (the dual of a ring), or one of the graphs corresponding to the surface graph of a Platonic solid. It can be shown that these reductions never destroy a symmetry of the original graph, though (if labeling is ignored) they may create new symmetries. The symmetry group of the surface graph can, thus, be derived from the reduced graph, and the vertex, edge, or face intersected by a given line can be found by backtracking the reduction. The polyhedron can have lines of symmetry only where its surface graph does, but not all symmetries of the surface graph need be symmetries of the polyhedron. It will be shown that once the symmetry group of the surface graph is known, all symmetries of the polyhedron can be found in linear time. There

25 are three cases. If the symmetry group of the surface graph is (k) for some k > 1, there is at most one axis, and it must intersect the polyhedral surface in the same place it intersects the surface graph. We can then use the axial symmetry test (algorithm 3a) to check that axis. If the symmetry group of the surface graph is one of (2,2,2), (2,3,3), (2,3,4) or (2,3,5), then the graph has a finite number of possible lines of symmetry. Therefore applying the axial symmetry algorithm to each line costs only linear time. This leaves only the case where the symmetry group of the graph is (2,2,k) for some k > 2. Let a be the line corresponding to the k -fold line of symmetry for the graph. Let z1 and z2 be the first and last intersections between line a and the surface of the polyhedron (these must be vertices or centroids of edges or faces). Let a be the plane perpendicular to a at the midpoint of (z1,92). The actual rotational symmetry of line a can be tested in linear time with algorithm 3a. However applying algorithm 3a to each of the other lines would require a total of e(n2) operations, since there may be e(n) such lines. We know from the surface graph that any other lines must be two-fold lines. Any symmetry transform around one of these lines must map the point z1 into the point z2, since we know from the surface graph that they cannot be similar to any other points on the polyhedron. All other lines must thus lie in the plane a, even if the line a is only a one-fold line of symmetry.

26 Theorem 3.5: Reflection and Rotation in Polyhedra: If a is a line, and a is the plane perpendicular to the line, then for any line b in a which intersects a, there exists some angle 0 such that R,, Cb,(P) = P if and only if P has a two-fold of symmetry c in plane a. [Proof] If c is a two-fold axis of symmetry for P then P = C2(P) Let c be the plane containing c and perpendicular to ia. Since it forms a 00~ angle with a. We can write P = Z,1 Z,(P) Let b be the plane containing b and perpendicular to a'. Since all reflection transforms are self-inverse, P Z-., Z, Z,, Z,,(P) c and b must both contain a. If they intersect at an angle O/ 2 then P = R,'Z,, z Z,1(P). b is perpendicular to a and both contain line b, so P = Rso~ Cb,2(P) If we assume that this relation holds for some P with no line of symmetry c, the reversal of the this above argument leads to a contradiction. | Using this theorem, we can find all lines of rotation perpendicular to line a by rotating the polyhedron 180~ about any line perpendicular to a and then using the cycle similarity algorithm to find if there are any rotations about a under which the rotated polyhedron is similar to the original. In this way, all k

27 possible lines of symmetry perpendicular to the graph's k-fold line can be tested in linear time. Once we have the lines of symmetry, it is not difficult to find all involutions under which the polyhedron is symmetrical. We can test for all involutions Zb,k through a plane b by reflecting the object through that plane, and using the cycle similarity algorithm to determine if any rotation about the line perpendicular to b aligns the reflected object with the original object. This test is linear. Polyhedra with lines in classes (2,2,2), (2,3,3), (2,3,4) or (2,3,5) have at most a constant number of possible planes of symmetry, so all can be tested in linear time. Polyhedra with lines in classes (k) and (2,2,k) may have two types of involutional symmetry. First, there may be involutions through the plane perpendicular to the k-fold line. This plane can be tested as above. Second, there may be k planes of reflectional symmetry which contain the k-fold line. These can be detected with the same algorithm that was used to find lines of symmetry for two-dimensional polygons. There remains only the case of polyhedra with no lines of rotational symmetry. These may habe at most one plane of involutional symmetry. Its location may be guessed from the surface graph's summetry group as in the previous paragraph, or if the surface graph has rotational symmetry group (1), the location may be proposed by using the graph isomorphism algorithm to find isomophisms betwen the surface graph and its reflection.

28 We find then, that it is possible to locate all symmetries for a poliyhedron with a connected, planar surface graph in linear time. For general polyhedra and three-dimensional point sets we have seen that the axial symmetry algorithm requires 0 (n logn ) time. To find all symmetries for these objects we use the surface graph of the convex hull to propose lines. The convex hull can be found in (n logn) time (Preparata and Hong 1977). This leads to an (n logn) algorithm for these objects. Unfortunately, the graph isomorphism algorithm of Hopcroft and Wong is very complicated and has a rather large constant. Although that algorithm could be somewhat simplified for this application, its use may be impractical. Conclusion It has been shown that, for polygons and polyhedra with connected, planar surface graphs, all symmetries can be detected in linear time. For point sets, and general polyhedra, e(n logn) time is required. The e(n logn) algorithms can be quite easily extended to a wide variety of geometrical structures without increasing the complexity. All these algorithms have been shown to be optimal. While the asymptotic behavior of the algorithms is good, the threedimensional cases share a rather large constant because they require a graph isomorphism test. Thus, the full three-dimensional symmetry algorithms are of primarily theoretical interest. The axial symmetry tests, however, are both practical and useful.

29 Acknowledgement The authors would like to thank Professor John H. Remmers for his assistance with one of the theorems in this paper. References Aho AV, Hopcroft JE, Ullman JD, (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley: Reading Akl SG, (1978) Comments on: G. Manacher, An Application of Pettern Matching to a Problem in Geometrical Complexity. Inf Proc Lett, 7:86 Bykat A, (1979) On Polygon Similarity. Inf Proc Lett, 9:23-25 Davis LS, (1977) Understanding Shape: II. Symmetry. IEEE Systems Man and Cybernetics, 7:204-212 Friedberg SA, Brown CM, (1984) Finding Axes of Skewed Symmetry. In: Proc IEEE Conf on Patt Recog, 322-325. Harary F, (1969) Graph Theory. Addison-Wesley: Reading Hopcroft JE, Wong JK, (1974) Linear Time Algorithm for Isomorphism of Planar Graphs. in Proc 6th Annual ACM Symp on Theory of Computing, 172184 Johansen R, Jones N, Clausen J, (1984) A Method for Detecting Structure in Polyhedra. Pattern Recognition, 2:217-225. Knuth DE, (1981) The Art of Computer Programming: Seminumerical Algorithms. Addison-Wesley: Reading Knuth DE, Morris JH, Pratt VR, (1977) Fast Pattern Matching in strings. SIAM J Computing, 6:323-350

30 Lee DT, Preparata FP, (1984) Computational Geometry -- A Survey. IEEE Trans Computers, 33:1072-1101. Lockwood EH, Macmillan RH, (1978) Geometric Symmetry. Cambridge University Press: Cambridge Manacher GK, (1976) An Application of Pattern Matching to a Problem in Geometrical Complexity. Inf Proc Lett, 5:6-7 Martin GE, (1982) Transform Geometry: An Introduction to Symmetry. Springer-Verlag: New York Parvi SK, Dutta Majumder D, (1983) Symmetry Analysis by Computer. Pattern Recognition, 16:63-67 Preparata FP, Hong SJ, (1977) Convex Hulls of Finite Sets of Points in Two and Three Dimensions. Communications ACM, 20:87-93 Tanimoto SL, (1981) A Method for Detecting Structure in Polygons. Pattern Recognition, 13:387-394 Wolter JD, Volz RA, Woo TC, (1985) Automatic Generation of Gripping Positions. IEEE Trans Systems Man & Cybernetics, to appear