TR#: | MSC-2006-01 |

Class: | MSC |

Title: | d-Dimensional Variants of Heilbronn's Triangle Problem |

Authors: | Jonathan Naor |

Supervisors: | Gill Barequet |

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.

To the list of the MSC technical reports of 2006

To the main CS technical reports page