Isometric and affine copies of a set in volumetric Helly results

Abstract: We show that for any compact convex set

K

in

m a t h b b R^{d}

and any finite family

m a t h c a l F

of convex sets in

m a t h b b R^{d}

, if the intersection of every sufficiently small subfamily of

m a t h c a l F

contains an isometric copy of

K

of volume

1

, then the intersection of the whole family contains an isometric copy of

K

scaled by a factor of

(1 - v a r e p s i l o n)

, where

v a r e p s i l o n

is positive and fixed in advance. Unless

K

is very similar to a disk, the shrinking factor is unavoidable. We prove similar results for affine copies of

K

. We show how our results imply the existence of randomized algorithms that approximate the largest copy of

K

that fits inside a given polytope

P

whose expected runtime is linear on the number of facets of

P

.

Recommendations

Cites work

This page was built for publication: Isometric and affine copies of a set in volumetric Helly results