A subset coloring algorithm and its applications to computer graphics.

A Subsect Coloring Algorithm and Its Applications to Computer Graphics

1. INTRODUCTION

Consider a monochrome bitmap device on which we wish to display diagrams like those in Figures 1 and 2. Many graphics packages (e.g., QuickDraw) contain primitive operations that can

* change all pixels within a given circle to white ("paint");

* Change all pixels within a given circle, changing white pixels to black and vice versa ("invert").

It is natural to ask whether we can obtain the configurations of Figures 1 and 2 by a sequence of paint and invert operations, starting from the configuration where all circles are colored white. It is perhaps surprising that we can generate Figure 1 but not Figure 2.

To create Figure 1 starting from the all-white configuration, we first invert circle 1, then we paint circle 2, and finally we invert circle 1 again.

Now let us prove that the configuration of Figure 2 is unreachable. Let us lable the regions as in Figure 3.

Let the color white be represented by 0 and black by 1. We represent a configuration C by an assignment of 0's and 1's to the variables x.sub.1, dx.sub.2, x.sub.3, x.sub.12, x.sub.13, x.sub.23, x.sub.123, in Figure 3. We then consider the following polynomial: f(C) = (x.sub.1 + x.sub.12 + x.sub.13 + x.sub.123) * (x.sub.2 + x.sub.12 + x.sub.23 + x.sub.123) * (x.sub.3 + x.sub.13 + x.sub.23 + x.sub.123) = X.sub.1X.sub.2X.sub.3, where X.sub.i represents the sum of all terms associated with circle i.

When all the regions are originally colored white, the value of f(C) is 0 (mod 2). We assert that if f(C) * 0 (mod 2) before an operation, then f(C) * 0 (mod 2) after than operation. This is clearly true for paint operation, which merely sets one of the terms of the product to 0.

Now we consider the invert operation. Since the product X.sub.1X.sub.2X.sub.3 * 0 (mod 2), at least one of the three terms must be congruent to 0 (mod 2). Without loss of generality, assume it is X.sub.1. If we invert circle 1, then we add 1 to each term of X.sub.1, which preserves the value of X.sub.1 (mod 2). If one of the other circles is inverted, say circle 2, then we add 2 to X.sub.1, since X.sub.1 and X.sub.2 share exactly two terms in common. This also preserves the value of X.sub.1 (mod 2).

Hence we have shown that we can never reach a configuration in which f(C) * 1 (mod 2). But this is exactly the case in Figure 2, which is therefore unreachable by any sequence of paint and invert operations. (In this particular case, it can be shown that the converse is true; namely, a configuration is reachable iff f(C) * 0 (mod 2).)

In this article we give a simple polynomial-time algorithm that decides whether a given configuration is reachable, and if so, produces a "short" sequence of operations to generate it.

2. A SUBSET COLORING ALGORITHM

We now describe a generalization of the problem which is independent of any geometric embedding. Let n be a positive integer and consider the set P.sub.j of all subsets of J = [1, 2, . . . , n]. We are given a subset S of P.sub.j - [[phi]] as input, along with an assignment of "colors" (0 = white; 1 = black) to S. This assignment of colors will be represented as an |S|-dimensional vector C(S) indexed by elements of S. (Here |S| denotes the number of elements in the set S.)

Let S.sub.j denote the set of subsets of S which contain the number j. (Informally, we refer to S.sub.j as the jth "circle".) Let E(S.sub.j) denote the characteristic vector for the set S.sub.j (with 1's corresponding to the subsets in S.sub.j dand 0's elsewhere).

To illustrate these definitions, consider the configuration of Figure 2. Here we have n = 3 and S = [, , , [1, 2] [1, 3], [2,3], [1, 2, 3]].

The vectors C(S) and E(S.sub.j) for [is less than or =] j [is less than or =] 3 are given below: S = [   [1, 2] [1, 3] [2, 3] [1, 2, 3]] C(S) = 0 0 0 0 0 0 1 E(S.sub.1) = 1 0 0 1 1 0 1 E(S.sub.2) = 0 1 0 1 0 1 1 E(S.sub.3) = 0 0 1 0 1 1 1

Our permissible operations are

* P.sub.j: Set C(S.sub.j) := 0 for some j (i.e., "paint circle j white");

* I.sub.j: Set C(S) := C(S) + E(S.sub.j) (mod 2) for some j (i.e., "invert circle j").

We will write an invert operation on circle j as I.sub.j and a paint operation as P.sub.j. Since order is unimportant when many operations of the same type are done consecutively, we can abbreviate a list of distinct invert operations I.sub.j1 I.sub.j2 . . . I.sub.js as I.sub.j where J = [j.sub.1, j.sub.2, . . . , j.sub.s], and similarly for the paint operation. When we list a sequence of operations, the leftmost is performed first.

We will prove the following:

THEOREM 1. Given an assignment of colors C(S), we can determine in time polynomial in |S| and n if that configuration is reachable. Further, if the configuration is reachable, we can find a sequence of O(n.sup.2) paint and invert operations to generate the configuration.

PROOF. We give an algorithm that attempts to find, in reverse order, the sequence of operations to generate the given configuration. There are two possibilities: the algorithm may find that the configuration is unreachable, in which case it terminates and says so. Otherwise, the algorithm produces a sequence of operations, which, taken in reverse order, will generate the given configuration.

First, let us consider the simple case where only invert operations are allowed. Then asking whether a configuration is reachable is the same as asking whether C(S) is in the GF(2)-span of the vectors [E(S.sub.j) |1 [is less than or =] j [is less than or =] n]. (GF(2) denotes the finite field of 2 elements.) This can easily be determined in polynomial time using Gaussian elimination over GF(2), in O(n.sup.2 |S|) bit operations.

Now we must consider the case where both paint and invert operations are allowed. The fundamental idea is to determine on which circle the last paint operation was done. We do this by testing each circle in turn. If C(S.sub.j) is not in GF(2)-span of the vectors [E(S.sub.j * S.sub.k) |1 [is less than or =] k [is less than or =] n] then circle j could not have been the last to be painted white, and we go to the next j. If, however, we succeed in writing for a set K, then we can "undo" this series of invert operations by doing an operation I.sub.k. Now we have reached a new configuration in which circle j is all white; we may discard all the sets S.sub.j from our attention and see if the remaining configuration C(S') is reachable. We claim the original configuration C(S) is reachable iff the new configuration C(S') is reachable. One direction is trivial, for we obtain C(S) from C(S') by painting circle j white and then doing the set of operations I.sub.K. On the other hand, suppose C(S) were reachable, possibly by some completely different sequence of operations. Then by doing the set of operations I.sub.K to C(S) we obtain a configuration which is identical to C(S') on all circles but circle j. Therefore, we could also obtain C(S'). (To put it another way, the sequence P.sub.j.I.sub.K is invertible on all sets of the configuration except those contained in circle j.)

This discussion gives an iterative algorithm for determining if a configuration is reachable. Formally, the algorithm is given as follows: produre Reachable(J, S, C(S)); comment J is an index set (e.g., the algorithm is originally called with J = [1, 2, . . . , n]]; S is a subset of P.sub.J - [[phi]]; C(S) is a coloring of S. undecided := true; white (|J| [is not =] 0) and undecided do begin K := J; reduced := false; while (|K| [is not =] 0) and (not reduced) do begin Pick a k from K; if C(S.sub.k) is in the GF(2)-span of the vectors E(S.sub.j * S.sub.k) (j * J) then begin Express C(S.sub.k) as a linear combination [sigma]t*T E(S.sub.k * S.sub.t); [push("invert circles in T");] [push("paint circle k");] S := S - S.sub.k; J := J - [k]; reduced := true; end else K := K - [k] end; [At this point, either |K| = 0 or reduced is true.] undecided := reduced; end; if (undecided) then print ("Configuration reachable") else print ("Configuration unreachable"); end. [Reachable]

Notice that if the input configuration is reachable, then the algorithm actually traces through the series of steps needed to reach that configuration, in reverse order. Thus, if we have a stack and perform the two push operations inside the comment symbols, then popping the stack at the end will list the sequence of paint and invert operations in the correct order.

To bound the running time of this algorithm, it may be necessary at the first step to check all n circles to discover which one was painted white last. Then the algorithm is called again, with a configuration of n - 1 circles. Continuing in this fashion, we use a total of (n+1 2) Gaussian eliminations, which gives a bound of O(n.sub.4 |S|) total bit operations. *

(In the special case where we are considering intersecting circles in the plane, we can use the well-known fact that n circles intersect to form at most n.sup.2 - n + 1 distinct regions ([3, p. 225]). Thus |S| = O(n.sup.2), which gives an O(n.sup.6) algorithm.)

Although we will show below that most configurations are not reachable, we can show that many of the configurations likley to arise in planar diagrams are in fact reachable:

COROLLARY 1. Any configuration S in which no subset is common to more than two S.sub.i is reachable.

PROOF. By induction on n, the size of the index set J. The reader can easily verify this for n = 1 and n = 2. Now assume true for all n < N. We are given a configuration of size N. Pick any circle S.sub.j and let K be the index set corresponding to circles which intersect S.sub.j in a black region. More formally, put K = [k| C(S.sub.j * S.sub.k) = 1].

Then since no subset is common to more than two S.sub.j, the configuration has an all-white circle S.sub.j, and is reachable if and only if C(S) is reachable. From the proof of correctness of the algorithm, we can discard the variable j and all subsets which contain it in S', and this new configuration C(S") on an index set of size N - 1 is reachable if and only if C(S) is reachable. But C(S") is reachable by induction, which completes the proof. *

COROLLARY 2. Any reachable configuration can be obtained using at most (n+2 2) - 1 paint and invert operations. Further, the sequence T of operations can always be put into a normal form (possibly by renumbering) such that T = P.sub.1I.sub.J1P.sub.2I.sub.J2 . . . P.sub.nI.sub.Jn where J.sub.k * [1, 2, . . . , k].

PROOF. Left to the reader. *

Notice that if S = P[1,2, . . . ,n] - [[phi]], then there are 2.sup.2n-1 possible configurations. The algorithm shows that only a vanishingly small fraction of them are reachable by a sequence of paint and invert operations:

COROLLARY 3. Let R.sub.n denote the number of reachable configurations on n circles. Then 2(n+1 2) [is less than or =] R.sub.n [is less than or =] 2(n+1 2) . n!

PROOF. The lower bound follows from Corollary 1. For the upper bound, we use Corollary 2. There are 2.sup.1 . 2.sup.2 . . . 2" ways to choose the sets J.sub.1, J.sub.2, . . . , J.sub.n and n! ways to renumber the circles themselves. *

We do not know an exact value for R.sub.n, although we have computed the first four values: n R.sub.n/1 2 2 8 3 112 4 5856

It can be shown that our upper bound on the number of Gaussian eliminations required by the algorithm is tight, in the sense that there exist configurations that require the algorithm to examine [omega](n.sup.2) circles. Similarly, there exist configurations that require [omega](n.sup.2) paint and invert operations to be colored. The details can be found in .

3. A GENERALIZATION AND ITS APPLICATIONS

As we have seen, the principal subroutine of the algorithm is writing a vector as a linear combination of a set of vectors. The algorithm requires at most (n+1 2) calls to this subroutine. It is easy to see that essentially the same algorithm works in other algebraic structures such as Z, Z/mZ, R. etc. Here we generalize the invert operation I to I.sub.a j: C(S) := C(S) + aE(S.sub.i); where a is any member of the algebraic structure.

Many graphics packages allow the use of "patterns," which are rectangular arrays of black and white pixels. Not only do they allow filling of areas with these patterns; they also allow filling that is a boolean function of both the "source" and "target" pixels. Processors for color graphics generally represent the colors as bit strings, and again allow bitwise boolean operations on these strings.

This suggests the following generalization of the algorithm. Let D be a principal ideal domain and let M be a finitely generated module over D. Then by a well-known theorem, M can be written as a direct sum of cyclic modules M = DZ.sub.1 * DZ.sub.2 * . . . * DZ.sub.2. (Thus the module is of rank s.) We then allow operations of the following form:

* ("Paint") C(S.sub.i) := C(S.sub.i) * W, where the projection of w into each of its coordinates is either 0 or 1. (Here represents coordinatewise "multiplication.")

* ("Invert") C(S) := C(S) + aE(S.sub.i), where a * M.

Then a simple modification of the algorithm will work and use (n+1

2)s calls to the linear combination subroutine. We discuss this in detail only for the case where M = (Z/2Z) * (Z/2Z) * . . . * (Z/2Z), which corresponds the case usually found in color graphics displays. Here the generalized paint operation corresponds to bitwise AND and the generalized invert operation corresponds to bitwise XOR.

Let b be a bit string and let S represent the current contents of the screen. Most color processors allow operations of the form S := b OP S, where OP is an arbitrary boolean function. However, it is easy to see that by combinations of the two operations S := b AND S S := b XOR S we can generate all of the 16 possible Boolean functions of two variables, where the left argument b can be any one of 0, 1, b, or NOT b.

THEOREM 2. Let the situation be as in Section 2, except that we are given a coloring represented by an assignment C(S) of bit strings of length K. Let b represent an arbitrary bit string of length K. Let the valid operations be

* P.sup.b.sub.j: Set C.sub.j(S) := b AND C.sub.j(S);

* I.sup.b.sub.j: Set C.sub.j(S) := b XOR C.sub.j(S).

The we can determine in O(Kn.sup.4|S|) bit operations if a given configuration is reachable, and if so, find a sequence of O(Kn.sup.2) operations to generate it.

PROOF. It should be noted that a configuration is reachable iff it is reachable in each of its K coordinates. Thus we may run the algorithm on each coordinate. Then we use a trick to determine the sequence of operations to generate the configuration, which is to use bit strings b of the form 11 . . . 11011 . . . 11 when performing the AND operations, and 00 . . . 00100 . . . 00 when performing the XOR operations. This has the effect of "masking" out all coordinates but the kth.

This gives a bound of O(Kn.sup.2) on the number of instructions needed to generate the configuration, if it is reachable.
COPYRIGHT 1988 Association for Computing Machinery, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Title Annotation: Printer friendly Cite/link Email Feedback algorithms and data structures Rubinstein, David; Shallit, Jeffrey; Szegedy, Mario Communications of the ACM technical Oct 1, 1988 2891 Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem. TABLET: personal computer in the year 2000. Color Data structures Problem solving