General nature of algorithms on part/image structure

In the section on the data structure I motivated the development of the "part/image" structure with the idea that the data structure should closely mimic the hierarchical pattern embodied in the face lattice of a polytope. This, in turn, has a bearing on how we think about algorithms that work on the data structure. Suppose we want to do something with a polytope P such as draw it on the screen- specifically, we want draw_polytope() to produce a wireframe image of the polytope. For this, we need to draw the one-dimensional faces (edges) of the wireframe. Assuming we have a function draw_edge() to draw the edges, how do we get to all the edges in the polytope efficiently? The following pseudo-code shows one solution: 
draw_polytope(p) {
   for each face f of p {
      if not done(f) {
         if dim(f) >  1
            draw_polytope(f)
         else
            draw_edge(f)
      }
   }
   done(f) <-- true
}
As is evident from the above example, the part/image data structure lends itself to recursive processing. The recursive solution is not necessarily the most efficient one, its just that recursive approaches are especially easy to implement given the nature of the data structure. This example also shows how done is used to avoid doing work twice.

Here's a similar example. Suppose we want to do a projection of a polytope, and suppose we have a function xform(p) which takes a part p and alters coord(p) according to the transformation of the projection. As with the previous example, the recursive implementation is simple: 

project_polytope(p) {
   for each face f of p {
      if not done(f) {
         project_polytope(f)
      }
   }
   xform(p)
   done(f) <-- true
}
The base case of the recursion is at the vertices. Vertices have no faces, so no further calls to project_polytope() are made.

Following is a more interesting (though equally contrived) example. Let's say we have the data structure representing a polytope P and we want to duplicate it so we have a second representation distinct from the first (and suppose that we've never heard of the C function memcpy() or anything like it). Suppose two 2-d faces share an edge and one face has already been duplicated. How does the second face access the duplication of the shared edge already obtained during the first face's duplication? This is where the result pointer comes in: 

duplicate_polytope(p) {
   for each face f of p
      if not done(f)
         duplicate_polytope(f)
   create part r
   copy color, location, dimension info from p into r
   create under r an image list to point to each result(f)
   result(p) <-- r
   done(p) <-- true
}
Here's an illustration of the process:
duplication
Note that if you are working on a polytope P, it may be that some or all of the faces F have been duplicated already, in which case done is true for f and result(F) has been set accordingly. Regardless of whether the faces were processed in this call to duplicate_polytope() or in some earlier call, the image list is made to point to each result(F).

Now that we've seen the use of result for duplicate_polytope(), there is no reason the diagram above can't be used to illustrate any operation that starts with one polytope and results in a second. Taking slices is one such operation.

(back to Contents)
(on to Cross-sections)