Heilbronn Triangle Problem

Speaker: 

Time: 

Friday, 1 February 2019, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

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.