Directional Convexity

Several alternative notions of convexity arise in different areas of mathematics. One particularly interesting and intricate example is rank-one convexity, or more generally directional convexity. These notions are relevant in calculus of variations for constructing solutions to certain systems of partial differential equations (see e.g. (Morrey, 1952), or the lecture notes (Kirchheim, 2003)), and in cryptography for determining the existence (and, if possible, constructing) of secure protocols for two-party communication (Basu et al., 2025). In this context, one is interested in requiring convexity of a set only in certain directions.

More precisely, let $D \subset \mathbb{R}^d$ be a cone, that is, a set such that for every $x \in D$, also $\lambda x \in D$ for all $\lambda \ge 0$. Then we can define analogues of the convex hull in two different ways.

Definition (Lamination hull)

Let $K \subset \mathbb{R}^d$ be a set and $D \subset \mathbb{R}^d$ be a cone. For every $i\geq 0$ define \begin{equation} K^{(i+1,D)} = \{ \lambda a + (1-\lambda)b \mid a,b \in K^{(i,D)}, a-b \in D, 0 \leq \lambda \leq 1\}, \end{equation} with $K^{(0,D)}=K$. The lamination hull of $K$ is defined as $K^{(\infty,D)}$.

Definition ($D$-convex hull)

Let $K \subset \mathbb{R}^d$ be a set and $D \subset \mathbb{R}^d$ be a cone. The $D$-convex hull of $K$ is \begin{equation} \operatorname{conv}_D(K) = \{ x \in \mathbb{R}^d \mid f(x) \leq \max_{y \in K} f(y) \text{ for all } f : \mathbb{R}^d \to \mathbb{R} \; D\text{-convex}\}, \end{equation} where a function $f : \mathbb{R}^d \to \mathbb{R}$ is said to be $D$-convex if its one-dimensional restrictions $t \mapsto f(x + t y)$ are convex functions for all $x \in \mathbb{R}^d$ and all $y \in D$.

Notice that if $D = \mathbb{R}^d$, we recover the standard notion of convexity, and both the lamination hull and the $D$-convex hull coincide with the usual convex hull. In general, we have the containment \begin{equation} K^{(\infty,D)} \subseteq \operatorname{conv}_D(K) \subseteq \operatorname{conv}_{\mathbb{R}^d}(K). \end{equation} On the other hand, if $\mathbb{R}^d = \mathbb{R}^{n \times m}$ and $D$ is the cone of the $n \times m$ rank-one matrices, we recover the notion of rank-one convexity.

The geometry of directional convexity, even for finitely many points, is still poorly understood, and explicit constructions are rare. This is partly because the definition involves infinitely many constraints, and because phenomena that do not occur in standard convexity arise: for example, the Carathéodory number is usually infinite in this setting.

Figure 1: Left: the lamination hull $K^{(\infty,D)}$ of five points (black dots) in the plane for $D=\{xy(y-\frac{2}{3}x)=0\}$.
Right: the rank-one convex hull of five triangular $2 \times 2$ matrices (black dots) embedded in $\mathbb{R}^3$.

Nevertheless, existing examples do not look too scary (see Figure 1) and suggest that the lamination hull and the $D$-convex hull of finitely many points might be semialgebraic, that is, definable by Boolean combinations of polynomial inequalities. This has been proven in special cases, such as rank-one convexity for diagonal matrices (Franěk & Matoušek, 2009), as well as in a few other settings (Matoušek & Plecháč, 1998). In most of these cases, the hulls are in fact unions of polytopes. In the last couple of years, new nonlinear examples and results have been studied in (Basu et al., 2025), (Basu et al., 2025), (Meroni & Bogdan, 2025).

Theorem (Corollary 1 of (Basu et al., 2025))

Let $D = \mathbb{R}^a \times \{0\}^b \times \mathbb{R}^c \cup \{0\}^a \times \mathbb{R}^b \times \mathbb{R}^c$ for some $a,b \in \{1,2,\ldots\}$ and $c \in \{0,1,2,\ldots\}$. For any finite set of points $K \subseteq \mathbb{R}^{a+b+c}$ the lamination hull $K^{(\infty,D)}$ is semialgebraic.

Theorem (Theorem 1.4 of (Meroni & Bogdan, 2025))

The rank-one convex hull of any set of finitely many $2 \times 2$ triangular matrices is semialgebraic.

The latter result provides a new explicit nonplanar, nonlinear family of examples whose hulls remain stable under small perturbations (Figure 1, right). Previously known nonlinear cases typically required that some of the points lie on a specific hypersurface, often a hyperboloid. Despite the affirmative results, the construction in (Meroni & Bogdan, 2025) suggests that, in certain settings, semialgebraicity of the $D$-convex hull may fail. This motivates the following conjecture.

Conjecture 34 (Existence of wild $D$-convex hulls)

The $D$-convex hull of a finite set of points is not necessarily semialgebraic.

In particular, a concrete example of a non-semialgebraic $D$-convex hull is conjectured to exist for any cone $D$ consisting of three distinct planes in $\mathbb{R}^3$ which all intersect in a line. This leads to the following problem.

Open Problem 35 (Conditions for semialgebraic $D$-convex hulls)

Determine under which conditions on $D \subset \mathbb{R}^d$ the $D$-convex hull of finitely many points is a semialgebraic set.

It would be very interesting to develop algorithms to compute $D$-convex hulls in the semialgebraic cases, as is done in (Basu et al., 2025) for certain classes of lamination hulls.

References

1. Morrey, C. B., Jr. (1952). Quasi-convexity and the lower semicontinuity of multiple integrals. Pacific Journal of Mathematics, 2, 25–53.
2. Kirchheim, B. (2003). Rigidity and Geometry of Microstructures. Max Planck Institute for Mathematics in the Sciences. https://www.mis.mpg.de/publications/preprint-repository/lecture_note/2003/issue-16
3. Basu, S., Amini Khorasgani, H., Maji, H. K., & Nguyen, H. H. (2025). Solving linear inequalities over convex sets & its applications to cryptography and hydrodynamics. Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS).
4. Franěk, V., & Matoušek, J. (2009). Computing D-convex hulls in the plane. Computational Geometry. Theory and Applications, 42(1), 81–89.
5. Matoušek, J., & Plecháč, P. (1998). On functional separately convex hulls. Discrete & Computational Geometry, 19(1), 105–130.
6. Basu, S., Khorasgani, H. A., Maji, H. K., & Nguyen, H. H. (2025). Solving Linear Inequalities over Convex Sets and its Applications to Cryptography and Hydrodynamics. Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2025).
7. Meroni, C., & Bogdan, R. (2025). Semialgebric rank-one convex hulls: 2x2 triangular matrices and beyond. ArXiv Preprint ArXiv:2509.07541.