The On-Line Heilbronn's Triangle Problem in d Dimensions

Alina Shaikhet

Heilbronn's triangle problem asks for the maximal possible area of the smallest-area triangle formed by n points in the unit square. The generalization of this problem to d dimensions is formulated as follows: Given n points in the d-dimensional unit cube, what is the maximum possible volume of the smallest d-dimensional simplex defined by some d+1 of these points?

In the on-line version of the triangle problem the value of n is not specified in advance. In other words, the points are positioned one after the other in a d-dimensional unit cube, while n is incremented by one after every point-positioning step. The procedure can be stopped at any time, and the already-positioned points must have the property that every subset of d+1 points defines a polytope whose volume is at least some quantity, where the goal is to maximize this quantity.