Minimum Convex Partitions and Maximum Empty Polytopes

Details Minimum Convex Partitions and Maximum Empty Polytopes Minimum Convex Partitions and Maximum Empty Polytopes

2011-12-05

arxiv.org/abs/1112.1124v1

Computer Science

Computational Geometry

Scientific paper

Let S be a set of n points in d-space. A convex Steiner partition is a tiling of CH(S) with empty convex bodies. For every integer d, we show that S admits a convex Steiner partition with at most (n-1)/d tiles. This bound is the best possible for affine independent points in the plane, and it is best possible apart from constant factors in every dimension d>= 3. We also give the first constant-factor approximation algorithm for computing a minimum Steiner convex partition of an affine independent point set in the plane. Determining the maximum possible volume of a single tile in a Steiner partition is equivalent to a famous problem of Danzer and Rogers. We give a (1-epsilon)-approximation for the maximum volume of an empty convex body when S lies in the d-dimensional unit box [0,1]^d.

Affiliated with

Also associated with

No associations

Rating

Minimum Convex Partitions and Maximum Empty Polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Convex Partitions and Maximum Empty Polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Convex Partitions and Maximum Empty Polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-380037