The position of individual boundary elements relative to the whole object is represented using two types of information. One is the order of elements around the boundary, and the other is the record of any places where an element is in proximity to another element on the same object, as determined by the proximity transform described in the previous section. The proximity transform, in which the object is also ``expanded'' with outlines inside the shape boundary, produces a canonical distance ordering for object interior distance that is consistent with the description of exterior distance. Note that the transform does not have the same interpretation for motion planning in this case, since there is no possibility that the boundaries of a rigid object will come into contact.
Internal proximity such as this is recorded in the partial distance ordering, with a tag to indicate that the elements are part of the same object. Boundary order is represented with a pointer from each boundary element to its left and right neighbours. The resulting representation of the boundary is a doubly-linked circular list, containing alternate segments and junctions.
This description of the boundary representation is slightly simplified, in that it omits the mechanism for multiple levels of detail on the object boundary. It is possible to represent sections of the boundary in multiple ways by allowing a number of parallel alternative sections of boundary. To achieve this, each boundary element does not have just a single pointer to its neighbours on the left and right, but a list of pointers, ranked in order from elements which are part of the coarse detail to those which are fine detail. The circular boundary list is therefore actually a network, when the multiple levels of details are considered, but it can be used as a simple list at a given level of detail by traversing the links at that level only. In the course of my implementation, I found that the two most useful ways to search the boundary are at the most coarse and most fine levels of detail.