Journal
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
Volume 42, Issue 1, Pages 81-89Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.comgeo.2008.03.003
Keywords
Directional convexity; D-convexity; Separate convexity
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available