On functional separately convex hulls. (English) Zbl 0892.68102

Matoušec, J.; Plecháč, P.

Discrete Comput. Geom. 19, No. 1, 105-130 (1998).

Summary: Let \(D\) be a set of vectors in \(\mathbb{R}^d\). A function \(f:\mathbb{R}^d\to \mathbb{R}\) is called \(D\)-convex if its restriction to each line parallel to a nonzero vector of \(D\) is a convex function. For a set \(A\subseteq \mathbb{R}^d\), the functional \(D\)-convex hull of \(A\), denoted by \(\text{co}^D(A)\), is the intersection of the zero sets of all nonnegative \(D\)-convex functions that are 0 on \(A\).
We prove some results concerning the structure of functional \(D\)-convex hulls, e.g., a Krein-Milman-type theorem and a result on separation of connected components.
We give a polynomial-time algorithm for computing \(\text{co}^D(A)\) for a finite point set \(A\) (in any fixed dimension) in the case of \(D\) being a basis of \(\mathbb{R}^d\) (the case of separate convexity).
This research is primarily motivated by questions concerning the so-called rank-one convexity, which is a particular case of \(D\)-convexity and is important in the theory of systems of nonlinear partial differential equations and in mathematical modeling of microstructures in solids. As a direct contribution to the study of rank-one convexity, we construct a configuration of 20 symmetric \(2\times 2\) matrices in a general (stable) position with a nontrivial functionally rank-one convex hull (answering a question of K. Zhang on the existence of higher-dimensional nontrivial configurations of points and matrices).

MSC:

68U05

Computer graphics; computational geometry (digital and algorithmic aspects)

Keywords:

functional \(D\)-convex hulls; rank-one convexity; \(D\)-convexity