There and back again: Split and prune to tighten

摘要

A regular paving is a finite succession of bisections that partition a root box x in ℝ^d into sub-boxes using a binary tree-based data structure. The sequence of splits that generate such a partition is given by the sub-boxes associated with the nodes of the tree. The leaf boxes, i.e., the sub-boxes associated with the leaf nodes, form a partition of x. We provide algorithms to tightly enclose the range of a function g : x → ℝ using its interval extension g. Our idea is to (i) refine the regular paving partition of the domain x by splitting the leaf boxes, (ii) obtain range enclosures of g over them, (iii) propagate the range enclosures of the leaf boxes up the internal nodes of the tree and finally (iv) prune back the leaves to get a coarser partition with fewer leaf boxes but with tighter range enclosures. This approach allows one to obtain tighter range enclosures for interval inclusion functions.