Heilbronn Triangle Problem

Siddharth Bhandari
Anamay Tengse
Friday, 1 Feb 2019, 17:15 to 18:15
A-201 (STCS Seminar Room)
Abstract: For a set $S$ of $n$ points in the unit square $U$, let $T(S)$ be the minimum area of a triangle whose vertices are three distinct points of $S$. Let $T(n)=max T(S)$ where $S$ ranges over all set of $n$ points in U. Heilbronn conjectured that $T(n)=O(1/n^2)$. This was disproved by Komlos, Pintz and Szemeredi (1982), who showed via a probabilistic argument that $T(S)=\Omega(\log{n}/n^2)$. We will first see two simpler proofs for $T(S)=\Omega(1/n^2)$ and then dwell into KPS'82. If time permits we will also discuss a possible approach to improve this bound.