This article is cited in 1 paper

Operations on the tree representations of piecewise quasi-affine functions

S. A. Guda

Faculty of Mathematics, Mechanics and Computer Science, Southern Federal University

Abstract: The piecewise quasi-affine (PQAF) functions and PQAF-sets are considered. Tree representation of PQAF-function and PQAF-set and its complexity are introduced. The algorithms of union, intersection, empty check, sum, image/preimage calculation, inversion, composition, and comparison are given. The algorithms are provided with complexity estimates of the resulting objects. A theorem about the type and complexity of lexicographical extrema in the PQAF-set, depending on the parameters, has been proved.

Keywords: piecewise quasi-affine function; quasi-affine selection tree; lexicographical extremum; Z-polytope.