Tata Institute of Fundamental Research
Heilbronn Triangle Problem
STCS Student Seminar
Speaker:
Siddharth Bhandari
Organiser:
Anamay Tengse
Date:
Friday, 1 Feb 2019, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Siddharth Bhandari |
| Organiser: | Anamay Tengse |
| Date: | Friday, 1 Feb 2019, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.