Bounding boxes

Select some fixed `n` and basis `\vec{e_i}, 1 lt i le n` of `RR^n`.

Define a relation `⊴` on points in `RR^n` such that `a ⊴ b` iff `forall i: (a.p_1 * \vec{e_i}) le (b.p_1 * \vec{e_i})`. Then (`RR^n`, `⊴`) is a poset, and in fact is also a lattice: the meet `a ^^ b` is merely the point `sum_{i=1}^n [ \vec{e_i} * max(a * \vec{e_i},b * \vec{e_i})]`, and the join is the same, with `min` substituting for `max`.

Let a bounding box be a set of points `B sube RR^n` such that a point `p in RR^n` is in `B` iff `vvv B ⊴ p ⊴ ^^^ B`. Intuitively (using the standard basis for `RR^n`), this is an axis-aligned closed box. A bounding box is uniquely defined by its `⊴`-infimum and `⊴`-supremum. (Note that these two points may be equal if `B` is the singleton set containing only that point; this is a perfectly legal bounding box.)

The relation `sube` defines a poset on the set `bbb B` of bounding-boxes, simply because it also defines one on the powerset of `RR^n`. We may use `sube` to extend `bbb B` into a join-semilattice: the join of two boxes `A` and `B` is the box defined by the `⊴`-infimum and `⊴`-supremum of `A uu B`.

The join is not always in `bbb B`, but we can extend `bbb B` to a complete lattice `bbb B^+` by adding two additional special bounding boxes not defined by their `⊴`-infimum and `⊴`-supremum: the nil box `bot = O/` and the world box `top = RR^n`. Then `(bbb B^+,sube)` is a proper lattice, in which the join is still defined as above (with global supremum `top`), and the meet is merely the intersection. Technically only `bot` is needed to make `bbb B^+` a lattice, but the inclusion of `top` makes it a bounded lattice, which is useful.

---

From a practical perspective, a bounding box may be conveniently represented as a pair of `n`-tuples of IEEE floats. Naively it might appear that we need an additional two bits — one to mark a degenerate case, and the other to distinguish between the two such — but with a small amount of cleverness in the representation, we can avoid both the additional two bits and the need for any special logic in the implementation of meet, join, or containment-of-point.

Specifically, we represent `top` as the pair of `n`-tuples `(-infty,-infty,...,-infty),(+infty,+infty,...,+infty)`, and `bot` as any pair `(a,b)` such that `a⋬b`, possibly with a canonical form `(+infty,+infty,...,+infty),(-infty,-infty,...,-infty)`. The large class of representations of `bot` makes equality testing slightly more difficult, but equality is a much rarer operation to perform on bounding boxes than meet, join, and containment. The natural implementations of binary meet on nondegenerate boxes (taking the min of each element of the left two tuples, and the max of each element of the right two), binary join (as meet, with max and min reversed), and containment-of-point (left[i] <= point[i] && point[i] <= right[i] for all i) naturally work with these as well.

Note that if we are working with integer boxes instead of floating-point, we cannot typically use `infty` as a value. However, most applications for integer bounding boxes involve an implicit universe of discourse (the size of the screen or what-have-you), and where this does not hold, -MAX_INT and MAX_INT will probably still do in practice.