M.Sc Student Shaikhet Alina The On-Line Heilbronn's Triangle Problem in d Dimensions Department of Computer Science Professor Gill Barequet Abstract

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 Hd off-line(n), 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 Hd on-line(n), where the goal is to maximize this quantity. In this thesis we show a lower bound for the on-line version of Heilbronn's triangle problem in d dimensions. Specifically, we provide an incremental construction for positioning n points in the d-dimensional unit cube, for which every simplex defined by d+1 of these points has volume Ω(1/n (d+1) ln(d-2) - 0.265d + 2.269) (for d ≥ 5). We generalize this result to k-dimensional simplices. That is, we show that every k-dimensional simplex, defined by k+1 of the n points in the d-dimensional unit cube has volume Ω(1/n(d+1) ln((d-2)/(d-k+1)) + 0.735d - k + 2.8881) (for d ≥ 5, d ≥ k ≥ 3).