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.