WorksMathematics
On Universal Minkowski Classes of Polytopes: Theory and Applications
Abstract
This paper establishes the existence, in every dimension, of universal Minkowski classes of configuration-constrained polytopes, with direct applications to set-theoretic control. For any prescribed accuracy, such a class contains an approximation of every compact convex set to that accuracy and admits a jointly affine parameterization of facets and vertices. The construction is explicit and relies on a combinatorial averaging procedure that produces minimal configuration enclosures. In control, these polytopic templates enable convex reformulations of otherwise non-convex problems, including invariant-set computation and control Lyapunov function design. Tutorial examples illustrate both the geometric construction and its control applications.
Introduction
Set-theoretic methods are widely used in the analysis and control of constrained dynamical systems [5]. Many of these methods rely on polyhedral computing [14, 25], since polytopes admit finite-dimensional representations, interact naturally with linear and convex optimization, and can approximate arbitrary compact convex sets to any prescribed accuracy [41]. In principle, modern optimization software makes it possible to manipulate polytopes with very large numbers of facets or vertices. Nevertheless, the optimization of a polytope itself remains difficult whenever both its facet and vertex representations enter the problem simultaneously.
This difficulty is fundamental in several set-theoretic control problems. Examples include the computation of robust control invariant sets, the construction of piecewise affine control Lyapunov functions, and the optimization of polytopic tubes in model predictive control [22, 21, 47, 26, 25]. In such problems, one would often like to parameterize a candidate polytope through its facet offsets, while dynamical conditions must be imposed at its vertices. However, the vertices generally depend nonlinearly and combinatorially on the facet offsets. Consequently, even when the underlying system is linear, the resulting optimization problem is typically non-convex.
For example, consider the computation of a robust control invariant set for a discrete-time linear system subject to additive disturbances. A natural candidate set can be described by fixing its facet normals and optimizing the corresponding offsets. The invariance conditions, however, must be verified at the vertices of the candidate polytope, whose locations and incidence structure vary with the offsets. The feasible set of offsets is therefore generally non-convex. For uncontrolled systems, this difficulty can sometimes be circumvented through specialized constructions [46]; in the controlled case, the simultaneous dependence on facets, vertices, and control actions remains a central obstacle.
Configuration-constrained polytopes provide a way to separate this geometric difficulty from the subsequent control optimization [47, 26]. Their defining feature is that the relevant facet–vertex incidence structure is fixed in advance. Within a prescribed configuration, both the facet offsets and the vertex coordinates admit a joint affine parameterization. As a result, conditions involving both representations can be expressed through convex constraints. Once an appropriate configuration has been selected, a number of otherwise non-convex set-theoretic control problems can therefore be reformulated as convex optimization problems.
This observation raises a fundamental approximation question. Fixing the configuration improves tractability, but it also restricts the admissible polytope geometries. It is therefore not immediate whether configuration-constrained polytopes retain enough flexibility to approximate arbitrary compact convex sets. Without such an approximation property, the restriction to a prescribed configuration could introduce an irreducible geometric conservatism, independently of the efficiency with which the resulting optimization problem is solved.
Figure 1. The set of polytopes that have the same facet normals as the left polytope is contained in the Hausdorff closure of the set of polytopes that have the same facet normals and the same face configuration as the right polytope. Therefore, we call the right polytope a configuration enclosure of the left polytope. In this paper, we show that every polytope admits such configuration enclosures, a result that can be used to address a variety of open problems in set-based robust and optimal control.
The main purpose of this paper is to resolve this question. In particular, it resolves the geometric approximation issue left open by the configuration-constrained tube-MPC and control-Lyapunov-function constructions in [47, 26]. We establish the existence, in every dimension, of universal Minkowski classes of configuration-constrained polytopes. More precisely, for every prescribed accuracy, we show that there exists a Minkowski class whose members admit a joint affine facet–vertex parameterization and approximate every compact convex set of unit diameter to within that accuracy. Thus, the geometric flexibility required for universal approximation is compatible with the fixed combinatorial structure needed for convex optimization.
Background and Related Work
The mathematical foundations of polyhedral theory originate in the work of Minkowski [35], Weyl [48], Carathéodory [8], and Farkas [11], among others. Subsequent developments revealed deep connections between convex polytopes, linear programming, combinatorics, and algebraic geometry [16, 9, 32]. Standard references on the geometric and combinatorial theory of polytopes include the monographs by Grünbaum [20] and Ziegler [49].
From a computational perspective, the conversion between facet and vertex representations is a central operation in polyhedral computing [18, 14]. Classical approaches include the double-description method [36], beneath-and-beyond procedures [44], and later refinements for vertex and facet enumeration [15]. Reverse-search methods introduced by Avis and co-workers provide an alternative framework for enumerating polyhedral objects while controlling memory requirements [1, 2]. These tools are highly developed, but their purpose is generally to enumerate or manipulate the geometry of a given polyhedron. They do not, by themselves, remove the non-convex dependence between the facets and vertices of a polytope whose geometry is being optimized.
Polyhedral methods have played a similarly important role in control. Gutman and Cwikel derived foundational vertex-based characterizations of control invariance for constrained linear systems [22, 21], while Bitsoris developed related algebraic conditions for invariant polytopes [3]. These results form part of the broader theory of set invariance developed and surveyed by Blanchini [4, 5]. More recently, Trodden showed that minimal robust positively invariant polytopes can be computed through convex optimization for an important class of uncontrolled uncertain systems [46]. Polyhedral techniques are also central to the analysis of parametric optimization problems arising in model-based control [27, 23].
In model predictive control [39], polytopes are routinely used to describe state and input constraints, terminal sets, reachable sets, and uncertainty tubes. Different restrictions on the geometry of the tube cross-sections lead to rigid, homothetic, elastic, and configuration-constrained tube MPC formulations [29, 37, 38, 47]. A recent survey of polyhedral methods in control, including their use in tube MPC and set-theoretic design, is provided in [25]. The present paper complements this literature by addressing a prior geometric question: whether the tractable class of configuration-constrained polytopes can, in principle, retain the universal approximation capabilities of unrestricted polytopes.
Contributions and Scope
The primary contribution of this paper is a foundational result in convex and polyhedral geometry. We prove that, for every dimension and every accuracy , there exists a Minkowski class of configuration-constrained -polytopes that is -dense in the family of compact convex subsets of with diameter 1. This result, stated in Theorem 1, shows that fixing a suitable facet–vertex configuration does not preclude approximation to arbitrary prescribed accuracy.
The proof is constructive. In particular, we introduce a combinatorial averaging procedure that generates minimal configuration enclosures and thereby produces the universal Minkowski classes used in the approximation theorem. The construction is presented in Algorithm 1 and analyzed in Theorem 2. Its role in this paper is primarily theoretical: it provides a finite and systematic construction establishing the existence of the required classes in every dimension. The procedure is deliberately general and is not intended as an optimized implementation. Its computational cost can be substantial, particularly in dimensions , and the development of specialized algorithms and data structures is left for future work.
The relevance to set-theoretic control arises after this offline construction has been completed. The resulting configuration-constrained templates combine two properties that are usually in tension: they admit a joint affine parameterization of facets and vertices, and they can approximate arbitrary compact convex sets to any prescribed accuracy. The first property enables convex reformulations of problems involving simultaneous facet and vertex constraints, while the second ensures that the use of such templates need not impose an intrinsic approximation barrier. In particular, the templates can be used in convex formulations for robust control invariant-set computation, control Lyapunov function design, and related polytopic optimization problems.
The construction is performed once, offline, for a given dimension and approximation accuracy. The resulting templates can then be stored and reused across different systems and control-design problems of the same dimension. Accordingly, the main contribution is not a new online control algorithm, nor a claim that the general construction is already computationally optimal. Rather, it is the constructive existence of universal configuration-constrained Minkowski classes and, through this result, a theoretical justification for using jointly parameterized polytopic templates in convex set-theoretic control formulations. The main developments are illustrated by means of tutorial examples.
Notation
Throughout this article, the standard terminology for sets is used. In particular, we use the following symbols:
denotes the -dimensional Euclidean space, and
denotes the set of nonempty compact convex sets in .
Additionally, the notion of partially ordered sets (posets) is used to describe the structure of set collections, such as the faces of a polyhedron. We use the standard notational conventions as in [49 Def. 2.5]. The Hausdorff distance, diameter, and Minkowski sum of are defined, as usual, by
and
Moreover, we recall the following standard definitions of Minkowski classes, see also [42 Chap. 3.5].
Definition 1 A set of compact convex sets is called a Minkowski class if it is closed in the Hausdorff metric and satisfies
for all and all .
Examples of Minkowski classes include the set itself, the class of centrally symmetric compact convex sets, and the set of zonoids; that is, the set of sets that can be approximated by a sum of line segments [43].
Definition 2. Let be two given set collections with . We say that is -dense in , for a given , if
The latter definition is important for analyzing generic numerical set approximation methods. Namely, in the context of approximating a set with a set , the constant in the above definition can be interpreted as a relative numerical approximation accuracy. Alternatively, if one scales the set such that , the constant can be interpreted as the absolute approximation accuracy.
Finally, the symbol denotes an all-ones vector whose dimension is clear from context. For vectors , we use the notation
to denote the convex hull. This notation is also used for matrices, where denotes the convex hull of the columns of .
Polytopes
The goal of this section is to introduce the basic definitions and properties of general polytopes and their face configuration.
Faces of Polytopes
Throughout this paper, we are interested in polytopes of dimension with at most facets. Let
denote the corresponding set of admissible facet matrices. The conditions require every row of to be nonzero and exclude positively collinear distinct rows. These restrictions involve no loss of generality when facet directions are prescribed, because zero normals and repeated positive directions can be removed. In this context, a polytope with facet matrix is a (potentially empty) set of the form
for some vector . In this context, the condition in the definition of is exactly the boundedness condition: it says that the facet normals positively span , or equivalently that the recession cone is . Thus, has no nonzero direction in which it can be unbounded; whenever it is nonempty, it is a bounded polyhedron, hence a polytope. As usual, we associate with each index set a face of , defined by
Faces of dimensions , , , and are called vertices, edges, -faces, and facets. The number of -faces of is denoted by . They are the components of the so-called -vector. Moreover, we recall that the faces of a polytope are a bounded and graded poset with respect to inclusion. It is called the face lattice of . In particular, we have
Generally, two polytopes are called combinatorially equivalent if their face lattices are isomorphic, see also [49 Chap. 2] for an in-depth discussion. Similarly, the following definitions are commonly used in almost all the literature on polytopes, see [20] and [49] for details.
Definition 3. A polytope in is called simple if all of its vertices are in exactly facets.
Definition 4. The facet representation with is called minimal, if .
We further recall that if is a minimal representation of a simple polytope, then the polytopes and are combinatorially equivalent for all vectors in a sufficiently small open neighborhood of , see [20 Section 4.5], [49 Section 2.5], and compare also [47 Cor. 2]. In other words, simple polytopes are locally configuration stable.
Configuration Posets
Throughout, we assume that is a given admissible facet matrix. We associate with each index set a nonempty convex cone,
In words, denotes the set of all parameters for which the face is nonempty. Note that is a closed polyhedral cone, whose lineality space is given by
To verify the inclusion , pick any , such that and . Then we can write
for some . Adding these two identities gives
Choosing with , which exists because , yields and, hence, . Therefore, ; see also [25]. Conversely, if , say , then via and via . Hence . Therefore,
Moreover, the set corresponds to the set of parameters for which . Additionally, we introduce the shorthand
The set is a convex cone and is the natural parameter domain for nonempty polytopes. Indeed, if , the support vector defined by
belongs to and satisfies . These cones can be used to analyze polytope configurations through the index-set collection
In words, denotes the collection of all index sets that correspond to the nonempty faces of a given polytope .
Definition 5. Let and be given. The configuration cone of a polytope is defined as
Additionally, two polytopes and with parameters are called configuration-equivalent for the given matrix , if .
Remark 1 Let be a polytope and let be a nonempty face of . Its normal cone is
The collection of the normal cones of all faces is the normal fan. A fan refines a fan if every cone of is contained in a cone of ; equivalently, is a coarsening of . Thus, refinement subdivides normal cones, whereas coarsening merges adjacent normal cones. For fixed facet-normal labels, parameters in the relative interior of one configuration cone have the same labeled normal fan. Moving to its boundary can merge normal cones, create additional facet incidences, make inequalities redundant, or produce a lower-dimensional degeneration. These notions are standard in the deformation- and type-cone literature; see [49, 42], [12 Sec. 1.1 and Cor. 1.42], and [25].
In the terminology of Remark 1, if is minimally represented, then precisely when the labeled normal fan of refines that of . The relative interior of therefore consists of parameters with the same labeled normal fan, whereas its boundary contains coarsenings, including cases with redundant inequalities or lower-dimensional degenerations. This is the configuration-cone form of the classical deformation/type-cone description; see [31 Thms. 8 and 10], [12 Cor. 1.42, Lem. 1.43, and Rem. 1.45], and [25]. Configuration-equivalent polytopes are necessarily combinatorially equivalent, but the converse need not hold; see Example 1. Moreover, configuration-equivalence is label-dependent. For example, if is obtained by permuting the rows of , then , although the indexed facet representation has changed. This dependence is natural in polyhedral computation, where the rows of the facet matrix and the corresponding face-index lists are stored explicitly.
The family of configuration cones is closed under finite intersections. In the type-cone description, the intersection of two chamber closures is either empty or a common face; whenever it is nonempty, that face is itself represented by the incidences active at a parameter in its relative interior. Thus,
is again a configuration cone. This construction and the definition below follow the type-cone-complex viewpoint of [31].
Definition 6 The poset of configuration cones associated with a matrix ,
partially ordered with respect to inclusion, is called the configuration poset of .
The poset is finite, because only finitely many collections can occur. Every configuration cone is a closed polyhedral cone with linearity space . Moreover, is the unique minimal element: every configuration cone contains it, while for every . Here, because implies . In contrast to a lattice, may have several maximal elements. We denote their number by .
Every maximal element has nonempty interior and can be written as
The representative can be chosen so that is a simple polytope with a minimal facet representation. These standard deformation/type-cone properties follow from [31, 12, 47, 25].
Configuration-Constrained Polytopes
Configuration-constrained polytopes were originally introduced in [47]. Using the notation of the current paper, they are defined as follows.
Definition 7 Let be a given facet matrix. For any , the associated class of configuration-constrained polytopes is
The class is nonempty because . It may, however, contain no simple polytopes unless represents a maximal element of . Regardless of simplicity, admits a double description: there exist vertex matrices such that
This was proved for maximal configuration cones in [47 Thm. 2] and extended to arbitrary configuration cones in [24 Prop. 1]. The following technical lemma summarizes a simple but relevant consequence of these results.
Lemma 1. Let and be given. Then is a Minkowski class (see Definition 1).
Proof. We first verify closedness. Let converge in the Hausdorff metric to . Since , every row of is supporting and
Continuity of support functions under Hausdorff convergence implies , where . The cone is closed, so . Passing to the limit in the common vertex representation (1) yields .
It remains to prove closure under Minkowski addition and nonnegative scaling. Let . Since is a convex cone, . For every ,
which implies
Conversely, the common vertex matrices in (1) imply that every can be written as
for suitable with . Hence,
Finally, since is a cone, for every and every . The same representation therefore gives
which proves closure under nonnegative scaling. □
Configuration Enclosures
While configuration-constrained polytopes provide a practical joint facet–vertex representation, it remains to determine whether such classes are sufficiently flexible to approximate arbitrary compact convex sets. The primary objective of this paper is to show that suitable configuration-constrained classes do possess this approximation property. Our main result can be formulated as follows.
Theorem 1. There exists for every and every dimension an integer and a matrix for which the Minkowski class is -dense in .
The proof of Theorem 1 is given in § 4.3. We first introduce the concept of configuration enclosures.
Outline of the Main Technical Idea
The main technical idea for proving Theorem 1 is to start with an arbitrary facet matrix and replace it with a configuration enclosure, defined as follows.
Definition 8. A facet matrix with is called a configuration enclosure of if
A given matrix may have many configuration enclosures; the enclosure matrix has facet normals. As follows from the normal-fan argument below, an enclosure must contain the original normal directions up to positive scaling, and hence . In the context of practical applications, however, we are interested in keeping the number of new facet normals, , as small as possible. Therefore, the following definition of minimal configuration enclosures is useful.
Definition 9. We call a minimal configuration enclosure of if there is no other configuration enclosure of that has fewer rows than .
Given these definitions, our strategy for proving Theorem 1 is to (i) recall the well-known fact that general polytopes can approximate arbitrary compact convex sets arbitrarily well [41] and (ii) replace such arbitrary polytopes by their configuration enclosures.
Monotypic Polytopes
It is useful to distinguish facet-normal configurations for which one maximal configuration class already contains every polytope representable with those normal directions. We call such configurations monotypic.
Definition 10. We call a matrix monotypic if it satisfies .
In words, monotypic polytopes are precisely those whose configuration poset has a unique maximal element. A polytope is called monotypic if represents this unique maximal element , that is, . Notice that Definition 10 is equivalent to the notion of monotype introduced in [33] relative to the set of normals of induced by the rows of .
Remark 2. Monotypy should be distinguished from strong monotypy, which requires the facet normals to determine the combinatorial type of the complete affine arrangement of the facet hyperplanes and therefore implies monotypy. Strong monotypy is equivalent to the generating property: every nonempty intersection of translates of the polytope is a Minkowski summand of the polytope [7, 34].
Some important examples of monotypic polytopes are collected in the proposition below.
Proposition 1. Every matrix is monotypic in each of the following cases:
and , or
and , or
and , or
, , and .
The corresponding monotypic polytopes are, respectively, all intervals with nonempty interior in , all simple polytopes in , all simplices with nonempty interior in any dimension, and all axis-aligned rectangular boxes with nonempty interior in any dimension.
Proof. The case and is trivial, as all intervals in with nonempty interior are configuration equivalent. Moreover, the fact that all simple polytopes in are monotypic follows from [47 Rem. 3]. Polytopes with facets and nonempty interior in are necessarily simplices, which can only have one possible configuration: any facets have a joint vertex. Finally, axis-aligned boxes are monotypic because every such -box is a direct product of one-dimensional intervals, reducing this case to the one-dimensional setting. □
Unfortunately, as much as it is remarkable that all simple polytopes in are monotypic, it turns out that the situation in dimension is very different. Namely, in dimensions , however, monotypy imposes nontrivial restrictions on the facet-normal configuration, and arbitrary normal configurations need not be monotypic. The following minimal example illustrates this obstruction.
Example 1 (Minimal non-monotypic polytope). Given Proposition 1, the simplest possible non-monotypic facet matrix must have columns and rows, because simplices are monotypic. One such matrix with the minimum possible numbers of rows and columns is
Namely, for this matrix, the sets and with
and
are both simple polytopes, but they are not configuration-equivalent1, as visualized below:
Figure 1 (PDF p. 9). .
Figure 2. .
The second and third facets of the left polytope have no joint vertex, whereas the second and third facets of the right polytope have two joint vertices. Of course, for such simple examples, we can still use our “geometric intuition” to construct a configuration enclosure. For instance, we can add one row to to construct the new matrix
which turns out to be a minimal configuration enclosure of . In fact, is even monotypic. For example, an associated monotypic polytope is obtained for ,
Figure 3. .
In addition to being monotypic, this polytope represents the Minkowski average
This example anticipates the Minkowski-averaging construction of minimal configuration enclosures developed next.
Combinatorial Averaging
This section develops a general method for constructing configuration enclosures and thereby provides a constructive proof of Theorem 1.
Minkowski Sums
Let be full-dimensional polytopes that admit a (potentially nonminimal) facet representation , . For , consider the weighted Minkowski average
The normal fan of a Minkowski sum is the common refinement of the normal fans of its summands. Consequently, the normal fan of is independent of the positive weights ; see [31 Sec. 6] and [42 Sec. 3.1]. Choose . After translating by and positively scaling the inequalities in a minimal facet representation, we may write
This normalization changes neither the normal fan nor the number of facets. The common-refinement property and the normal-fan characterization of configuration cones then imply
The following proposition records the corresponding boundary cases.
Proposition 2 Let , , be full-dimensional polytopes with , and let be a normalized minimal facet matrix satisfying (2). Then there exist vectors such that
Proof. The normal fan of is the common refinement of the normal fans of the summands and therefore refines the normal fan of each . Define the -support vector of by
Every facet-normal ray of is a ray of the common refinement, so . The normal-fan characterization of configuration cones further gives ; see [31 Thm. 8] and [25].
Combinatorial Averaging
The core strategy for constructing configuration enclosures of an arbitrary matrix is to construct the Minkowski average of its configurations. The corresponding method is summarized in Algorithm 1. The following
Algorithm 1 Combinatorial Averaging
Start with any matrix .
Pick for each maximal element a representative such that .
Form the Minkowski average
choose , and compute a normalized minimal facet representation
Return the matrix .
theorem establishes the fact that this procedure returns the minimal configuration enclosure of any given facet matrix.
Theorem 2 Algorithm 1 returns a minimal configuration enclosure of any given input matrix .*
Proof. Let , , and let be the normalized translate of their Minkowski average constructed in Step 3 of Algorithm 1. Proposition 2 implies that every belongs to .
Because , each is simple and minimally represented by . Hence every ray generated by a row of is a ray of the normal fan of each . The normal fan of is their common refinement and retains these rays. After a row permutation, we may therefore write

Figure 2 (PDF p. 11). LEFT: Eight simple polytopes, , which are not configuration equivalent. They correspond to all possible configurations that can be obtained for the facet matrix . RIGHT: the Minkowski average of these polytopes. To develop a geometric understanding of the exceptional adaptability of the face arrangement of the Minkowski average polytope depicted on the right, it is helpful to explore basic geometric manipulations achievable by pressing specific facets inward. Initially, consider the lower right polytope in the left panel, which has a triangular facet, oriented towards the viewer. By pressing this triangle inward, its vertices will eventually be blocked by the opposing vertices of the facet of the backside of the polytope. In stark contrast, pressing the hexagonal facet of the polytope on the right panel results in the convergence of the opposite edges of the adjacent rectangular facets. As the compression continues, these edges elongate until the three visible pentagonal facets degrade into points. Throughout this process, additional configuration constraints become active, but sufficient flexibility remains to further press the facet inwards, ultimately causing the entire polytope to degrade into a single point. It is worth noting that similar manipulations can be applied to other facets, allowing for the recovery of all eight polytopes on the left through a continuous deformation of the polytope on the right, without violating any configuration constraints.
Let satisfy . Replacing by its support vector, if necessary, does not change the polytope and ensures . Since the configuration poset is finite, is contained in a maximal element . Thus , and the normal fan of refines that of . By the common-refinement property, the normal fan of also refines that of . Define
Since the rows of include positive multiples of all rows of , the additional inequalities are valid support inequalities and . The normal-fan characterization gives . Therefore, is a configuration enclosure of ; see [31 Thm. 8] and [25].
It remains to prove minimality. Let be any configuration enclosure of . Then contains every . Lemma 1, together with closure under nonnegative scaling, implies that this class contains their Minkowski average. It is also translation invariant because is the lineality space of . Hence, it contains the normalized translate from Step 3. Thus, provides an -row facet representation of . Since is a minimal facet representation of this polytope, . Therefore, no configuration enclosure of has fewer rows than .
In particular, the proof shows that the enclosure matrix contains every original normal direction, possibly with a positive rescaling.
Example 2 (A configuration enclosure) The steps of Algorithm 1 are illustrated by the matrix
The first six rows of this matrix are the facet normals of the unit cube in , while the seventh row vector of is orthogonal to the convex hull of the first three row vectors of . Consequently, can be used to represent, for
example, the unit cube, and many other geometric objects that can be obtained by intersecting the unit cube with a coordinate-aligned simplex. A more in-depth analysis shows that there are 8 configuration cones with nonempty interior, corresponding to the 8 maximal elements of the poset . For example, the vectors
represent 8 different polytopes , . These polytopes are all simple and pairwise configuration-inequivalent with respect to the fixed row labels of , although some of them are combinatorially equivalent after relabeling their facets. Thus, if we initialize Algorithm 1 with , we can pick these vectors as representatives of the maximal elements of . Next, we work out the Minkowski average in Step 3) of Algorithm 1. After scaling the rows of appropriately, this yields
A corresponding (appropriately scaled) representative vector is given by
where contains the Minkowski average polytope. The translation and positive row scaling used in Step 3 merely normalize an interior representative to 1 and do not change these enclosure directions or the represented family. All simple polytopes in the Minkowski class have 10 facets in total. These facets always consist of 1 hexagon, 6 pentagons, and 3 rectangles; see Figure 2.
Remark 3 Minimal configuration enclosures need not be monotypic. In Example 1, the minimal configuration enclosure is monotypic, whereas the minimal configuration enclosure obtained in Example 2 is not, since admits more than one maximal element. In particular, the polytope with is simple and minimally represented by all rows of but it is not configuration-equivalent to , hence .
Proof of Theorem 1
Let
The Blaschke selection theorem implies that is compact in the Hausdorff metric; see [42 Sec. 1.8]. For each , classical polytope-approximation results provide a full-dimensional polytope satisfying
see [10, 6, 41]. Compactness yields finitely many sets whose Hausdorff balls of radius cover . Let collect all outward facet normals of the finitely many polytopes , after repeated positive directions have been removed. Since each is bounded and full-dimensional, its facet normals positively span ; hence, for some . Assigning the additional inequalities their support values gives a representation for every . Hence, for every , some satisfies
Translation and positive scaling extend this estimate to every with positive diameter: for , apply the normalized result to and use
Singletons are represented exactly because . Thus, the family of all polytopes is -dense in . Finally, Theorem 2 provides a configuration enclosure of . By definition, contains every nonempty polytope representable with and is therefore also -dense in . Renaming as proves the theorem.
Computational Scope and Offline Construction
Algorithm 1 has a primarily theoretical role. Together with Theorem 2, it provides a finite construction of a minimal configuration enclosure for every admissible facet matrix. As shown in the preceding subsection, this construction also completes the constructive proof of Theorem 1. Thus, Algorithm 1 establishes not only the existence of universal Minkowski classes, but also that they can, in principle, be generated by a finite procedure.
To make the enumeration step explicit, quotient the parameter space by the translation lineality and fix one positive scale. The maximal elements of then appear as the maximal cells of a finite type-cone, or chamber, subdivision. Two maximal elements are adjacent when their normalized cells share a codimension-one face. The resulting adjacency graph is finite and connected: the chamber fan is the normal fan of a secondary polyhedron, and its maximal cones are connected through facet adjacencies [12 Cor. 1.42 and Rem. 1.45]. A generic parameter in the relative interior of the normalized admissible domain supplies an initial maximal cell. Starting from this cell, one may therefore enumerate all maximal elements by generating the neighboring cells across its irredundant facets and traversing this graph with breadth-first or depth-first search; reverse search provides a memory-efficient alternative [2]. This supplies a finite enumeration scheme in principle, although constructing efficient local adjacency oracles and output-sensitive implementations remains beyond the scope of this paper.
This constructive result should not be interpreted as a claim that combinatorial averaging is the most efficient method for computing configuration enclosures. The desired object is the enclosure matrix , rather than the enumeration or the Minkowski average itself. Consequently, alternative constructions might generate a configuration enclosure—possibly a minimal one—without explicitly enumerating all maximal elements of or forming their complete Minkowski average.
The relevant computational tasks belong to a broad and active research area on output-sensitive enumeration methods for combinatorial and polyhedral problems. Representative developments include pivoting and reverse-search methods for polyhedra and hyperplane arrangements [1, 2], algorithms and complexity results for Minkowski sums [19, 13], and region-enumeration procedures in multiparametric programming [45]. These methods indicate several possible directions for specialized implementations of Algorithm 1, but developing and comparing such implementations is beyond the scope of this article.
The computational burden of Algorithm 1 has two principal sources: the enumeration of the maximal elements of and the construction of a minimal facet representation of their Minkowski average. A coarse bound on the size of the latter output can nevertheless be obtained. Since all representative polytopes share the same facet matrix , every edge direction is orthogonal to linearly independent rows of . Hence, the number of possible unoriented edge directions is at most
Moreover, every edge direction of the Minkowski average is inherited from an edge direction of one of its summands. Since a facet contains linearly independent edge directions, its normal line is determined by at most elements of this set. Therefore, the number of candidate facet-normal lines, where opposite normals are identified, satisfies
Consequently, without identifying opposite facet normals, the number of rows of admits the conservative bound
This is only an output-size estimate. In particular, it does not bound , the cost of enumerating the maximal configuration cones, or the possible growth of intermediate representations during the Minkowski-sum computation. It should therefore not be interpreted as a complete runtime-complexity bound for Algorithm 1.

Figure 3 (PDF p. 14). Visualization of a dodecahedron (left) and its minimal configuration enclosure (right). The closure of the set of polytopes that are configuration equivalent to the right polytope contains, beside many other interesting geometric objects, the famous ”soccer ball polytope”, consisting of 12 pentagonal and 20 hexagonal facets. It is obtained by pressing the hexagonal facets of the right polytope inwards, initially without changing the face lattice, until the opposite edges of the rectangular facets merge in the limit.
Example 3 (Dodecahedron). The conservatism of the preceding estimate is illustrated by Figure 3. The original dodecahedron has dimension and facets. Thus,
Equivalently, the general oriented-normal estimate gives
In contrast, Algorithm 1 returns a minimal configuration enclosure with only
facets. The enclosure consists of 12 decagonal, 20 hexagonal, and 30 rectangular facets. This example shows that the combinatorial estimate may overstate the actual output size by several orders of magnitude.
Once a suitable enclosure has been computed, the combinatorial construction need not be repeated in subsequent control applications. The resulting facet and vertex coefficient matrices can be stored and reused for different systems of the same dimension, or distributed as precomputed template libraries. The online polytopic optimization problems then use only the resulting jointly affine facet–vertex parameterization and do not invoke Algorithm 1.
Randomized exploration, symmetry reduction, incremental Minkowski-sum updates, and partial averaging may all be useful for reducing the practical computational effort. However, the exact guarantee of Theorem 2 relies on accounting for every maximal element of ; averaging only a sampled subset generally produces an uncertified candidate rather than a configuration enclosure. Finding efficient, preferably output-sensitive methods for computing minimal configuration enclosures therefore remains an open problem and is beyond the scope of the present manuscript.
Open Problem: Adversarial Convex Bodies
Theorem 1 establishes the existence of configuration-constrained Minkowski classes with arbitrarily small approximation error. For a prescribed class , its worst-case approximation error can be defined as
Since is invariant under translations and positive scalings, the outer supremum may equivalently be restricted to sets satisfying
This normalized family is compact in the Hausdorff metric, while the distance to the closed class is continuous. Consequently, the supremum is attained. We call any corresponding maximizer an adversarial convex body for the class .
The geometric properties of such adversarial convex bodies remain largely open. In particular, it is not clear whether an adversarial convex body can always be chosen to be polyhedral, whether its dimension or combinatorial complexity can be bounded in terms of and , or how its exposed directions are related to the prescribed facet configuration. For a fixed , the inner minimization can be treated using the joint facet–vertex parameterization (1). The principal difficulty is the global optimization over . Structural characterizations and certified computational methods for determining would provide a quantitative basis for comparing different configuration cones and their configuration enclosures.
Applications of Universal Minkowski Classes
Optimization over compact convex sets arises in shape optimization, robust design, uncertainty quantification, and learning-based safety; see, for example, the Galerkin framework in [40] and set-based approaches to safe learning in [28, 30]. The main focus of this article, however, is set-theoretic control, where polytopes are routinely used to represent invariant sets, reachable sets, robust tubes, and polyhedral control Lyapunov functions.
This section explains how the approximation result of Theorem 1 connects with convex computational methods in control. The key object is a configuration triple , which provides a finite-dimensional parameterization in which both facets and vertices depend affinely on the same decision variables. A broader account of the corresponding control formulations can be found in [25, 26].
Minkowski-Convex Set Optimization
Consider an optimization problem whose decision variable is a compact convex set,
A functional is called Minkowski-convex if
for all and . Problem (4) is therefore a convex optimization problem in the natural linear structure induced by Minkowski addition and nonnegative set scaling. Several relevant examples are collected below.
Example 4 (Polytopic inclusions) For a fixed direction , the support function
is Minkowski-affine, because
Consequently, maxima of affine expressions involving support functions are Minkowski-convex. This observation is particularly useful for representing set-containment constraints. For example, if
then the functional
is Minkowski-convex and satisfies
Example 5 (Volume functionals). A standard objective to maximize the volume of sets in is given by
The Brunn–Minkowski inequality implies [17, 42]
Thus, is Minkowski-convex. Notice that the negative volume itself is not, in general, Minkowski-convex when .
Example 6 (Distance functionals). For a fixed point , the set-distance functional
is Minkowski-convex. Indeed, choosing as nearest points to gives
More generally, for a fixed compact convex set , both the directed set distance
and the Hausdorff distance
are Minkowski-convex as functions of . These functionals provide natural measures of set-inclusion violation and geometric approximation error; see also [40].
Example 7 (Invariance constraints). The preceding properties can be combined to formulate robust control-invariance conditions. Consider
where and are compact and is convex. Define
This functional is Minkowski-convex. To see this, let
and write an arbitrary as
For controls that attain, or arbitrarily closely approximate, the inner minima, define
For every , convexity of the distance under simultaneous Minkowski combinations yields
Taking successively the maximum over , the minimum over the control, and the maximum over the state gives
Moreover, since the distance is nonnegative, it holds that
These examples cover the main ingredients of many set-theoretic control problems: geometric size objectives, approximation errors, state-set containment, and robust invariance. Thus, such problems can often be expressed in the Minkowski-convex form (4); see [47, 25] for further examples. The remaining difficulty is that optimization over is infinite-dimensional. The following subsection explains how universal configuration-constrained Minkowski classes provide finite-dimensional convex discretizations of these problems.
Restoring Convexity to Polytopic Parameterizations
Problem (4) is infinite-dimensional. A natural finite-dimensional approximation is obtained by fixing a facet matrix and parameterizing the decision set as . This yields
Although finite-dimensional, this problem is generally non-convex. Indeed, as varies, the vertices and face-incidence structure of may change. Functionals involving both its facet and vertex representations therefore become piecewise-defined or disjunctive in the parameter .
This difficulty is removed by restricting the parameters to a configuration cone. Let
Such a finite polyhedral representation follows from the configuration-cone construction; see [47, 25]. The resulting discretization is
On , the facets and vertices of admit a joint affine parameterization. More fundamentally, the set-valued mapping is affine with respect to Minkowski combinations:
for all and . Hence, every Minkowski-convex functional induces a convex function
on the configuration cone. Consequently, Problem (8) is a finite-dimensional convex optimization problem. For many problems in set-theoretic control, its objective and constraints additionally admit explicit linear or conic representations.
Theorem 1 shows that imposing a configuration constraint does not create an intrinsic geometric approximation barrier: suitably chosen configuration-constrained Minkowski classes can approximate every compact convex set to arbitrary accuracy. Suppose that the functionals are Hausdorff-continuous, the feasible sets lie in a common Hausdorff-compact family, an optimal solution exists, and Problem (4) admits a strictly feasible solution. Minkowski combinations of an optimal and a strictly feasible solution yield strictly feasible sets with objective values arbitrarily close to the optimum. Density and continuity then imply convergence of the optimal values of increasingly accurate universal-template discretizations. Configuration constraints thus restore convexity without fundamentally sacrificing geometric expressiveness.
Example 8 (CI polytopes: convex formulation). We illustrate the use of configuration templates by computing control invariant inner approximations of the maximal control invariant set for the three-dimensional system
where the angle is measured in radians. The state and control constraints are given by
respectively.
The computation of a maximal control invariant set can be formulated as a Minkowski-convex optimization problem over compact convex subsets of . In this formulation, state-set containment and control invariance are imposed through the functionals introduced in Examples 4 and 7, respectively, while the objective is chosen as the volume functional
from Example 5.
As described in the preceding section, a finite-dimensional convex discretization is obtained by restricting the decision set to a Minkowski class . Using the equivalences in Examples 4 and 7, with , the feasible region
corresponds to the finite-dimensional polyhedron
Here, the vertex matrices provide the joint facet–vertex representation of the selected configuration class, which is represented by the matrix , compare [47 Sect. 3.5]. The first constraint enforces the invariance condition at the vertices, which is equivalent to enforcing , with ; see also [25]. In this context, the constraint restricts to the chosen configuration cone, and the constraints on ensure admissibility of the associated vertex controls. Similarly, and for all vertices are equivalent to ; that is .
Let be a set of index tuples enumerating the vertices of the simplices of a tetrahedralization of a representative polytope in the relative interior of the configuration cone. For each index tuple of a tetrahedron, order its vertices such that the corresponding determinant is positive at the representative, and define
Since the labeled face configuration is constant on the relative interior, the same vertex-index tetrahedralization applies there and
Thus, is a homogeneous cubic polynomial in , which extends continuously to the boundary of the configuration cone. Although this polynomial is not concave in general, its cube root is concave by the Brunn–Minkowski inequality.
Therefore, for each candidate class, the problem
returns a control invariant set with maximal volume. Here, we solve it for each of the eight maximal configuration cones
in Example 2 and its configuration enclosure. Consequently, every feasible solution of (10) defines a certified control invariant inner approximation of the maximal control invariant set. Alternative set-size objectives can also be used to select control invariant sets while preserving a linear-programming formulation; see, e.g., [25 Sections 3.1 and 3.2] for examples applied to reachable and positive invariant polytopes. Such objectives may be useful when a computationally simpler selection criterion is preferred over the volume-based objective.
Figure 4 shows the resulting control invariant inner approximations. The lighter enclosing polytope is the maximal control invariant set, while the darker polytopes are the inner approximations, of maximal volume, obtained from the eight maximal configuration cones of . The optimizer associated with

Figure 4. Eight nested polytope configurations. The inner polytopes are shown in gray, while their enclosing outer polytopes are displayed using a lighter gray and lower opacity.
is the top-left polytope in Figure 4 and has seven facets and ten vertices.
In this example, the optimizer obtained from the configuration-enclosure class happens to coincide with the optimizer obtained from the first configuration cone . Although a generic polytope in the enclosure class has ten facets, the optimal parameter lies on the boundary of its configuration cone. At this boundary point, some facet inequalities become redundant, and the resulting polytope reduces to the seven-facet configuration associated with . The results in Figure 4 show that for this example optimizing over the configuration enclosure yields a control invariant set whose volume is at least as large as that of the polytopes obtained from the basis configurations.
Conclusion
This paper has established that prescribing a fixed facet–vertex configuration creates no intrinsic geometric approximation barrier. For every dimension and every accuracy , Theorem 1 provides a configuration-constrained Minkowski class that is -dense in the compact convex sets. The combinatorial-averaging construction produces such classes through minimal configuration enclosures while retaining the joint affine facet–vertex parameterization required for convex computation. In set-theoretic control, this resolves a geometric question left open by earlier configuration-constrained tube-MPC and control-Lyapunov-function constructions [47, 26]: restricting a parametric polytope to one suitably chosen fixed configuration does not inherently sacrifice universal approximation capability.
The final section showed how invariant-set and related control problems can be cast as Minkowski-convex set-optimization problems and discretized through finite-dimensional convex parameterizations by configuration-constrained polytopes. More broadly, the theoretical results establish that such parameterizations can be made arbitrarily expressive and open several directions for further research, including the efficient construction of universal Minkowski classes, the structural and computational characterization of adversarial convex bodies, and the output-sensitive enumeration of maximal configuration cones.
Acknowledgement
The authors would like to thank Colin Jones for inspiring discussions during the first author’s research stay at EPFL in 2023. During these discussions, Colin Jones raised the question whether configuration-constraints fundamentally obstruct the approximation of convex bodies to arbitrary accuracy. This motivated the central problem addressed in this work. Our results confirm that, provided the configuration templates are chosen appropriately, no such obstruction exists.
References
- [1]D. Avis and K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Computational Geometry, 8:295–313, 1992.
- [2]D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65:21–46, 1996.DOI
- [3]G. Bitsoris. On the positive invariance of polyhedral sets for discrete-time systems. Systems and Control Letter, 11(3):243–248, 1988.DOI
- [4]F. Blanchini. Set invariance in control. Automatica, 35(11):1747–1767, 1999.DOI
- [5]F. Blanchini and S. Miani. Set-theoretic methods in control. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston, MA, 2015.
- [6]E.M. Bronshtein and L. D. Ivanov. The approximation of convex sets by polyhedra. Siberian Mathematical Journal, 16(5):852–853, 1975.
- [7]Vuong Bui. Every generating polytope is strongly monotypic. Discrete & Computational Geometry, 73(1):49–61, 2025.
- [8]C. Carathéodory. Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen. Rend. Circ. Mat. Palermo, 32:193–217, 1911.DOI
- [9]G.B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963.
- [10]R.M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory, 10(3):227–236, 1974.
- [11]J. Farkas. Theorie der einfachen Ungleichungen. Journal für die reine und angewandte Mathematik, 124:1–27, 1902.DOI
- [12]F. Fillastre and I. Izmestiev. Shapes of polyhedra, mixed volumes and hyperbolic geometry. Mathematika, 63(1):124–183, 2017.
- [13]K. Fukuda. From the zonotope construction to the minkowski addition of convex polytopes. Journal of Symbolic Computation, 38(4):1261–1272, 2004.DOI
- [14]K Fukuda. Polyhedral Computation. ETH Zürich Research Collection, 2020.DOI
- [15]K. Fukuda and A. Prodon. Double description method revisited. In M. Deza, R. Euler, and I. Manoussakis, editors, Combinatorics and Computer Science, pages 91–111. Springer, 1996.DOI
- [16]D. Gale. The Theory of Linear Economic Models. McGraw-Hill, New York, 1960.
- [17]R.J. Gardner. The brunn–minkowski inequality. Bulletin of the American Mathematical Society, 39(3):355–405, 2002.DOI
- [18]R. Graham and F. Yao. A whirlwind tour of computational geometry. American Mathematical Monthly, 97(8):687–701, 1990.DOI
- [19]P. Gritzmann and B. Sturmfels. Minkowski addition of polytopes: Computational complexity and applications to gröbner bases. SIAM Journal on Discrete Mathematics, 6(2):246–269, 1993.DOI
- [20]B. Grünbaum. Convex Polytopes. John Wiley & Sons, 1967.
- [21]P.-O. Gutman and M. Cwikel. An algorithm to find maximal state constraint sets for discrete-time linear dynamical systems with bounded controls and states. IEEE Transactions on Automatic Control, 32:251–254, 1987.DOI
- [22]P.O. Gutman and M. Cwikel. Admissible sets and feedback control for discrete-time linear dynamical systems with bounded controls and states. IEEE Transactions on Automatic Control, 31(4):373–376, 1986.
- [23]M. Herceg, M. Kvasnica, C. Jones, and M. Morari. Multi-parametric toolbox 3.0. In Proceedings of European Control Conference (ECC), pages 502–510, 2013.DOI
- [24]B. Houska, M.A. Muller, and M.E. Villanueva. On stabilizing terminal costs and regions for configuration-constrained tube MPC. IEEE Control Systems Letters, 8:1961–1966, 2024.DOI
- [25]B. Houska, M.A. Muller, and M.E. Villanueva. Polyhedral control design: Theory and methods. Annual Reviews in Control, 60:100992, 2025.arxiv.org/abs/2412.13082
- [26]B. Houska, M.A. Muller, and M.E. Villanueva. Control Lyapunov function design via configuration-constrained polyhedral computing. Automatica, 188:112896, 2026.arxiv.org/abs/2503.16076
- [27]C.N. Jones. Polyhedral Tools for Control. PhD thesis, University of Cambridge, 2005.
- [28]T. Koller, F. Berkenkamp, M. Turchetta, and A. Krause. Learning-based model predictive control for safe exploration. In Proceedings of the 57th IEEE Conference on Decision and Control, pages 6059–6066, 2018.arxiv.org/abs/1803.08287
- [29]W. Langson, I. Chryssоchoos, S.V. Raković, and D.Q. Mayne. Robust model predictive control using tubes. Automatica, 40(1):125–133, 2004.DOI
- [30]Y. Li, J. Yu, L. Conger, T. Kargin, and A. Wierman. Learning the uncertainty sets of linear control systems via set membership: A non-asymptotic analysis. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 29234–29265. PMLR, 2024.arxiv.org/abs/2309.14648
- [31]P. McMullen. Representations of polytopes and polyhedral sets. Geometriae Dedicata, 2:83–99, 1973.DOI
- [32]P. McMullen. The polytope algebra. Advances in Mathematics, 78(1):76–130, 1989.DOI
- [33]P McMullen, R Schneider, and GC Shephard. Monotypic polytopes and their intersection properties. Geometriae Dedicata, 3(1):99–129, 1974.DOI
- [34]Peter McMullen. On monotypic polytopes: P. mcmullen. Discrete & Computational Geometry, pages 1–16, 2026.DOI
- [35]H. Minkowski. Allgemeine Lehrsätze über die konvexen Polyeder, pages 121–139. Springer Vienna, Vienna, 1989.
- [36]S. Motzkin, H. Raiffa, G.L. Thompson, and R.M. Thrall. The double description method. In H.W. Kuhn and A.W. Tucker, editors, Contributions to Theory of Games, volume 2. Princeton University Press, 1953.
- [37]S. Raković, B. Kouvaritakis, and M. Cannon. Equi-normalization and exact scaling dynamics in homothetic tube model predictive control. Systems & Control Letters, 62(2):209–217, 2013.DOI
- [38]S. Raković, W.S. Levine, and B. Açıkmeşe. Elastic tube model predictive control. In American Control Conference (ACC), 2016, pages 3594–3599. IEEE, 2016.DOI
- [39]J.B. Rawlings, D.Q. Mayne, and M.M. Diehl. Model Predictive Control: Theory and Design. Madison, WI: Nob Hill Publishing, 2015.
- [40]J. Rieger. A Galerkin approach to optimization in the space of convex and compact subsets of ℝ^d. Journal of Global Optimization, 79:593–615, 2021.
- [41]R. Schneider. Zur optimalen Approximation konvexer Hyperflächen durch Polyeder. Mathematische Annalen, 256:289–301, 1981.DOI
- [42]R. Schneider. Convex bodies: the Brunn–Minkowski theory, volume 151. Cambridge University Press, 2013.
- [43]R. Schneider and W. Weil. Zonoids and related topics. In P.M. Gruber and J.M. Wills, editors, Convexity and Its Applications, pages 296–317. Birkhäuser, Basel, 1983.DOI
- [44]R. Seidel. A convex hull algorithm optimal for joint sets in even dimensions. Technical Report, University of British, Columbia Dept. of Computer Science Vancouver, 1981.
- [45]P. Tøndel, T.A. Johansen, and A. Bemporad. An algorithm for multi-parametric quadratic programming and explicit MPC solutions. Automatica, 39(3):489–497, 2003.
- [46]P.A. Trodden. A one-step approach to computing a polytopic robust positively invariant set. IEEE Transactions on Automatic Control, 61(12):4100–4105, 2016.DOI
- [47]M.E. Villanueva, M.A. Müller, and B. Houska. Configuration-constrained tube MPC. Automatica, 163:111543, 2024.arxiv.org/abs/2208.12554
- [48]H. Weyl. Elementare Theorie der konvexen Polyeder. Commentarii Mathematici Helvetici, 7:290–306, 1934.DOI
- [49]G.M. Ziegler. Lectures on Polytopes. Springer, 1995.



