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
PDFMSC-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}))$).
CopyrightThe 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.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion
admin