|M.Sc Student||Naor Jonathan|
|Subject||d-Dimensional Variants of Heilbronn's Triangle Problem|
|Department||Department of Computer Science||Supervisor||Professor Gill Barequet|
In the 1950's the Jewish German mathematician Hans Heilbronn posed the following question: what is the maximal area, over all configurations of n points in the unit square, of the smallest of the triangles formed by the points of the configuration?
In this thesis we show lower and upper bounds for a generalization of Heilbronn's triangle problem to d dimensions.
By a probabilistic construction we give a lower bound on the maximal minimum-area triangle formed by a configuration of n points in the d-dimensional unit cube. We then generalize the method to obtain a lower bound on the maximal minimum-volume k-dimensional simplex formed by a configuration of n points in the d-dimensional unit cube.
By combinatorial and graph-theoretic arguments we show upper bounds for both the triangle case and the k-simplex case.