OP-00048 Open

When are directional convex hulls semialgebraic?

Let $D \subseteq \mathbb{R}^d$ be a cone. A function $f : \mathbb{R}^d \to \mathbb{R}$ is $D$-convex if $t \mapsto f(x + ty)$ is convex for every $x \in \mathbb{R}^d$ and $y \in D$, and the $D$-convex hull of a finite set $K \subseteq \mathbb{R}^d$ is $$\operatorname{conv}_D(K) = \{x \in \mathbb{R}^d : f(x) \le \max_{y \in K} f(y) \text{ for every } D\text{-convex } f\}.$$ For $D = \mathbb{R}^d$ this is the convex hull; for the cone of rank-one matrices it is the rank-one convex hull. The hull of finitely many points is known to be semialgebraic in special cases: separate convexity, that is, rank-one convexity for diagonal matrices (Matoušek and Plecháč), finite sets of directions in the plane (Franěk and Matoušek), and the rank-one convex hull of finitely many $2 \times 2$ triangular matrices (Meroni and Raiță). For the lamination hull, which is contained in the $D$-convex hull, Basu, Amini Khorasgani, Maji and Nguyen proved that the lamination hull of any finite set is semialgebraic when $D = (\mathbb{R}^a \times \{0\}^b \times \mathbb{R}^c) \cup (\{0\}^a \times \mathbb{R}^b \times \mathbb{R}^c)$ with $a, b \ge 1$ and $c \ge 0$. The source conjectures that $D$-convex hulls of finite sets need not be semialgebraic.

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

Source: Meroni, Open Problem 35 of Randomstrasse101, in “Directional Convexity” (2026).

The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.

Classification

Primary: MG — Metric Geometry
Secondary: AG
Keywords: directional convexity, Randomstrasse101, rank-one convexity, semialgebraic sets
Literature checked: Oct. 2, 2026 by clemens-admin

References

@misc{meroni2026directional,
  author = {Meroni, Chiara},
  title = {Directional Convexity (problems 34 and 35)},
  howpublished = {Randomstrasse101 blog},
  year = {2026},
  url = {https://randomstrasse101.math.ethz.ch/posts/DirectionalConvexity/}
}

@misc{meroni2025rankone,
  author = {Meroni, Chiara and Rai{\c{t}}{\u{a}}, Bogdan},
  title = {Semialgebraic rank-one convex hulls: $2\times2$ triangular matrices and beyond},
  year = {2025},
  eprint = {2509.07541},
  archivePrefix = {arXiv}
}

@inproceedings{basu2025lamination,
  author = {Basu, Saugata and Amini Khorasgani, Hamidreza and Maji, Hemanta K. and Nguyen, Hai H.},
  title = {Solving linear inequalities over convex sets and its applications to cryptography and hydrodynamics},
  booktitle = {66th IEEE Symposium on Foundations of Computer Science (FOCS 2025)},
  year = {2025}
}

@article{franek2009dconvex,
  author = {Fran{\v{e}}k, Vojt{\v{e}}ch and Matou{\v{s}}ek, Ji{\v{r}}{\'\i}},
  title = {Computing {$D$}-convex hulls in the plane},
  journal = {Computational Geometry},
  volume = {42},
  number = {1},
  pages = {81--89},
  year = {2009},
  doi = {10.1016/j.comgeo.2008.03.003}
}

@article{matousek1998separately,
  author = {Matou{\v{s}}ek, Ji{\v{r}}{\'\i} and Plech{\'a}{\v{c}}, Petr},
  title = {On functional separately convex hulls},
  journal = {Discrete \& Computational Geometry},
  volume = {19},
  number = {1},
  pages = {105--130},
  year = {1998},
  doi = {10.1007/PL00009331}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00048, "When are directional convex hulls semialgebraic?", clopen.solutions.