Computing D-convex hulls in the plane

A function f:Rd→R is called D-convex, where D is a set of vectors in Rd, if its restriction to each line parallel to a nonzero v∈D is convex. The D-convex hull of a compact set A⊂Rd is the intersection of the zero sets of all nonnegative D-convex functions that are 0 on A. Matoušek and Plecháč provided an algorithm for computing the D-convex hull of a finite set in Rd for D consisting of d linearly independent vectors (in this case one speaks about separately convex hulls). Here we present a (polynomial-time) algorithm for the D-convex hull of a finite point set in the plane for arbitrary finite D.