Computing D-convex hulls in the plane

A function f : R-d -> R is called D-convex, where D is a set of vectors in R-d, if its restriction to each line parallel to a nonzero v is an element of D is convex. The D-convex hull of a compact set A subset of Rd is the intersection of the zero sets of all nonnegative D-convex functions that are 0 on A. Matousek and Plechac provided an algorithm for computing the D-convex hull of a finite set in R-d 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. (c) 2008 Elsevier B.V. All rights reserved.