The design of a new coordinate space consists mostly in the design of the XnRegions? which can be used to describe (possibly infinite) sets of positions in that coordinate space. It will generally not be the case (for a given coordinate space) that all mathematically describable sets of positions will be representable by an XnRegion in that space. This should not be seen as a temporary deficiency of the current implementation of a space, but rather part of the design of what a given space *means*.

For example, in IntegerSpace, one cannot form the XnRegion whose members are exactly the even numbers. If this were possible, other desirable properties which are part of the intent of IntegerSpaces? would no longer be possible. For example, any XnRegion should be able to break itself up into a finite number of simple XnRegions? ("simple" is described below). Were an even number region possible, this would have undesirable consequences for the definition of "simple" in this space. If you want (for example) to be able to have a XnRegion which can represent all the even numbers, it probably makes more sense to define a whole new space in which these new XnRegions? apply.

XnRegions? should be closed under a large set of operations, such as intersection, unionWith, complement and minus. ("closed" means that the result of performing this operation on XnRegions? of a given space is another valid XnRegion in the same space.) Additional guarantees are documented with each operation.

A XnRegion may be classified at one of three levels of "simplicity":

1) The simplest are the *distinctions*. Distinctions are those that answer with (at most) a single set containing themselves in response to the message "distinctions". (The reason I say "at most" is that a full region (one that covers the entire coordinate space) may answer with the empty set.) Distinctions are the simplest XnRegions? of a given space out of which all other XnRegions? of that space can be finitely composed. There should probably be a message "isDistinction" for which exactly the distinctions answer "true". The complement of a distinction is a distinction. Three examples of distinctions in spaces are:

a) in IntegerSpace, any simple inequality. For example, all integers < 37.

b) in one kind of 3-space, any half space (all the space on one side of some plane)

c) in another kind of 3-space, any sphere or spherical hole.

Note that "c" could not just have spheres as the distinction because distinctions must be closed under complement. (We are here ignoring the quite substantial problems that arise in dealing with approximate (e.g., floating point) which would almost necessarily have to arise in doing any decent 3-space. 3-space is nevertheless a good intuition pump.)

2) Next are the *simple regions*. Simple regions are exactly those that say "true" to "isSimple". All distinctions are also simple regions. In response to the message "distinctions", and simple region must return a finite set of distinctions which, when intersected together, yield the original simple region. Generally, one tries to define the simple regions for a space to correspond to some notion of locality in the space. For example, it may be good for a simple region not to be able to have a hole in it. Or perhaps a simple region is which must be connected (whatever that means in a given space). Example non-distinction simple regions for the above example spaces would be:

a) The interval from 3 inclusive to 17 exclusive (intersection of all integers >= 3 and all < 17)

b) A convex hull (intersection of half spaces)

c) Whatever you get by intersecting a bunch of spheres and sherical holes. The simple regions for both "a" and "b" would be connected, without holes, and even convex. This follows directly from the definition of our distinctions. None of these nice properties holds for "c", and this also follows directly from our decision to start with spheres. "c" is still perfectly valid, just less preferable by some criteria. 3) Finally, there are the regions of a space in general. Any region must respond to the message "simpleRegions" with a stepper which will produce a finite number of simple regions that, when unioned together, yields the original region. A simple region will return a stepper that will return at most itself ("at most" because an empty region (which covers no positions) may return an empty stepper). Example non-simple regions are:

a) all integers < 3 and all integers >= 17

b) two convex hulls

c) two disjoint spheres

Note that "a" is the complement of the earlier "a" example, thereby showing why the complement of a simple region isn`t necessarily simple. Even though the "c" space is so unconstrained in the properties of its simple regions, there is no way to interect a finite number of spheres and spherical holes to produce a pair of disjoint spheres. Therefore the pair is non-simple. Not all spaces must have non-simple regions (or even non-distinctions). It is interesting to observe for "b" and "c" that even though there is a natural conversion between their respective positions, (except for the empty and full regions) there is no conversion at all between their respective regions. The kinds of sets of positions representable in one space is completely different than those representable in the other space.

We will use these three example spaces repeatedly in documenting the protocol.