Computing \(D\)-convex hulls in the plane (Q950402)

The authors present an algorithm for computing the so called \(D\)-convex hull of a finite point set in the plane. A function is called \(D\)-convex if its restriction to each line parallel to a nonzero vector from a set of \(d\) vectors (directions) is convex. Unlike the separately convex hull where the set of direction vectors consists of linearly independent vectors (the standard basis in the \(d\)-dimensional space, for example), here a finite set of arbitrary nonzero direction vectors in the plane is considered. The principle of the suggested algorithm is described on a concrete planar example and explained by many pictures. The results can be used in the areas where the particular case of \(D\)-convexity, so called rank-one convexity, appears -- i.e. in calculus of variations, theory of partial differential equations, mathematical models of crystalline microstructure, etc.