Large triangles in the d-dimensional unit cube

We consider a variant of Heilbronn's triangle problem by asking for a distribution of n points in the d-dimensional unit cube [0,1]d such that the minimum (two-dimensional) area of a triangle among these n points is as large as possible. Denoting by and the supremum of the minimum area of a triangle among n points over all distributions of n points in [0,1]d for the off-line and the on-line situation, respectively, for fixed dimension d⩾2 we show that and for constants which depend on d only. Moreover, we provide a deterministic polynomial time algorithm that achieves the lower bound Ω((logn)1/(d-1)/n2/(d-1)) on the minimum area of a triangle among n points in [0,1]d in the off-line case.