# Technical Report MSC-2006-01

 TR#: MSC-2006-01 Class: MSC Title: d-Dimensional Variants of Heilbronn's Triangle Problem Authors: Jonathan Naor Supervisors: Gill Barequet PDF MSC-2006-01.pdf Abstract: Heilbronn's triangle problem asks for the maximal possible area of the triangle of smallest area formed by $n$ points in the unit square. In this thesis we show lower and upper bounds for a generalization of Heilbronn's triangle problem to $d$ dimensions. Namely, we show that there exists a set $S_1$ (resp., $S_2$) of $n$ points in the $d$-dimensional unit cube such that the minimum-area triangle (embedded in $d$ dimensions) defined by some three points of $S_1$ (resp., $S_2$) has an area of $\Omega(d^{1-1/(2(d-1))}/n^{2/(d-1)})$ (resp., $O(d/n^{2/d})$). We then generalize the applied methods and show that there exists a set $S_3$ (resp., $S_4$) of $n$ points in the $d$-dimensional unit cube such that the minimum-volume $k$-dimensional simplex (embedded in $d$ dimensions, for $2 \leq k \leq d$) defined by some $k+1$ points of $S_3$ (resp., $S_4$) has volume $\Omega(f(k,d) / n^{k/(d-k+1)})$, where $f(k,d)$ is independent of $n$ (resp.,$O(k^{k/d} d^{k/2} / (k! \, n^{k/d}))$). Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/MSC/MSC-2006-01), rather than to the URL of the PDF files directly. The latter URLs may change without notice.