Abstract : This paper is about the approximate representation of compact sets using subpavings, i.e., unions of non-overlapping boxes, and about computation on these sets, with particular attention to implementation issues. Some basic operations such as evaluating the intersection or union of two subpavings, or testing whether a box belongs to a subpaving are first presented. The binary tree structure used to describe subpavings then allows a simple implementation of these tasks by recursive algorithms. Algorithms are presented to evaluate the inverse and direct images of a set described by a subpaving. In both cases, a subpaving is obtained that is guaranteed to contain the actual inverse or direct image of the initial subpaving. The effectiveness of these algorithms in characterizing possibly nonconvex on even nonconnected stes is finally illustrated by simple examples.
Keywords : trees Binary trees bounded errors image evaluation recursive algorithms set inversion subpavings trees.