Overlap in Region Splay

[Mark S. Miller <vlad!mark>]

Dean & I talked about this last night, and we noticed something
interesting.  Given that the general purpose code in the ent for
splaying a region is something like:

aRegion distinctions stepper 
	forEach: [:distinction {Region} | 
		"do Ravi's region splay algorithm
		 using the region 'distinction'"
		...].

(Which translates to something like:

for (SPTR(Stepper) stepper = aRegion->distinctions()->stepper();
     stepper->hasValue();
     stepper->step()) {
	SPTR(Region) distinction = CAST(Region,stepper->value());
	/*do Ravi's region splay algorithm
	  using the region 'distinction' */
	...
}
)

Then, whether the resulting splay trees have overlap depends purely on
what kind of distinctions simple regions break themselves up into.
(The intersections of the "distinctions" regions should yield the
original) In a coordinate space where the simple regions are
orthogonal boxes, and they break themselves up into distinctions which
are half-spaces (in 3-space, a rectangular box would break itself up
into 6 half spaces), then we end up with a region splay without
overlap.  

How do we handle Mr. Hill's example of a space in which the
simpleRegions are spheres?  A possibility that is perfectly correct is
to have a sphere just report its set of distinctions as the one
element set consisting of the sphere itself.  The resulting splay
operation will create some amount of overlap (which will reduce
efficiency), but will work correctly.  It then becomes only a policy
decision in the design of the regions for a coordinate space whether &
how much overlap to have in it's splay trees.  The general purpose
code doesn't have to care.  Quite a pleasing modularity.

P.S. Ravi, in recalling a comment you made a few days ago, I realize
now you may have already known all this.