טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentNaor Jonathan
Subjectd-Dimensional Variants of Heilbronn's Triangle Problem
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet


Abstract

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.