There and back again: Split and prune to tighten

Raazesh Sainudiin, Jennifer Harlow, Warwick Tucker

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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.

Original languageEnglish
Title of host publicationFUZZ-IEEE 2013 - 2013 IEEE International Conference on Fuzzy Systems
Publication statusPublished - 22 Nov 2013
Externally publishedYes
EventIEEE International Conference on Fuzzy Systems 2013 - Hyderabad, India
Duration: 7 Jul 201310 Jul 2013
Conference number: 22nd (Proceedings)

Publication series

NameIEEE International Conference on Fuzzy Systems
ISSN (Print)1098-7584


ConferenceIEEE International Conference on Fuzzy Systems 2013
Abbreviated titleFUZZ-IEEE 2013
Internet address


  • Binary trees
  • Interval functions
  • Regular pavings

Cite this