Polygons in space

We are now considering 2 polygons P and Q. If these polygons are labelled, we can apply the same algorithm as in the case of labelled sets of points. This can also be done in O{n} time and space.

Figure 3

In the case of unlabelled polygons, There are only n possible ways to label a polygon, so we have only 2n possibilities of assigning the labels. By using the algorithm for labelled polygons, we can determine if the two polygons are photos of the same polygon in space in O(n2) time and space.

 

The reconstruction of polygons in space is illustrated in the applet.