Hadwiger conjecture (combinatorial geometry)

There also exists an equivalent formulation in terms of the number of floodlights needed to illuminate the body.

The conjecture remains unsolved even in three dimensions, though the two dimensional case was resolved by Levi (1955).

Formally, the Hadwiger conjecture is: If K is any bounded convex set in the n-dimensional Euclidean space Rn, then there exists a set of 2n scalars si and a set of 2n translation vectors vi such that all si lie in the range 0 < si < 1, and Furthermore, the upper bound is necessary if and only if K is a parallelepiped, in which case all 2n of the scalars may be chosen to be equal to 1/2.

This number is also sufficient: a cube or parallelepiped may be covered by 2n copies, scaled by a factor of 1/2.

Hadwiger's conjecture is that parallelepipeds are the worst case for this problem, and that any other convex body may be covered by fewer than 2n smaller copies of itself.

However, the conjecture remains open in higher dimensions except for some special cases.

The best known asymptotic upper bound on the number of smaller copies needed to cover a given body is[2] where

, while for bodies with a smooth surface (that is, having a single tangent plane per boundary point), at most

smaller copies are needed to cover the body, as Levi already proved.