mini|300px|Sechs Punkte im Einheitsquadrat. Die kleinsten Dreiecke (rot) besitzen den Flächeninhalt 1/8, den für sechs Punkte größtmöglichen Wert. Die Punkte bilden ein affines Bild eines regelmäßigen Sechsecks.

Das Heilbronnsche Dreiecksproblem ist eine Fragestellung der diskreten Geometrie. Gesucht ist eine Anordnung von Punkten in einem vorgegebenen Bereich der Ebene, etwa im Einheitsquadrat, bei der das flächenkleinste unter allen von je drei Punkten aufgespannten Dreiecken möglichst groß ausfällt. Benannt ist das Problem nach Hans Arnold Heilbronn, der vermutete, dieser größtmögliche Flächeninhalt nehme mindestens so rasch ab wie . Komlós, Pintz und Szemerédi widerlegten die Vermutung 1982. Die tatsächliche Wachstumsordnung ist bis heute unbekannt.

Problemstellung

Es seien eine kompakte konvexe Teilmenge der Ebene mit positivem Flächeninhalt und eine natürliche Zahl. Je drei der platzierten Punkte spannen ein Dreieck auf. Zu einer festen Punktkonfiguration betrachtet man das flächenkleinste der Dreiecke und fragt nach derjenigen Konfiguration, für die dieser Wert maximal wird. Da kompakt ist, wird das Maximum angenommen. Folglich gilt

wobei den Flächeninhalt des aufgespannten Dreiecks bezeichnet.

Für die Wachstumsordnung ist die Wahl von unerheblich. Sind und zwei konvexe Bereiche positiven Flächeninhalts, so enthält ein affines Bild von . Eine affine Abbildung multipliziert alle Flächeninhalte mit demselben Faktor, sodass sich und höchstens um einen von unabhängigen Faktor unterscheiden. In asymptotischen Aussagen schreibt man daher kurz .

Für festes hängt der exakte Wert dagegen von ab. Eingehend untersucht sind drei Fälle: das Einheitsquadrat, geschrieben , ein Dreieck vom Flächeninhalt eins, geschrieben , sowie der Fall, dass unter allen konvexen Bereichen vom Flächeninhalt eins auch der Bereich selbst optimal gewählt werden darf. Da je zwei Dreiecke affin äquivalent sind, ist im zweiten Fall die Gestalt des Dreiecks ohne Belang.

Heilbronns Vermutung und ihre Widerlegung

Heilbronn vermutete vor 1951, dass gilt, wobei ein Landau-Symbol ist. Dass diese Schranke, wenn sie zuträfe, nicht weiter verschärft werden könnte, zeigte Paul Erdős. Ist eine Primzahl, so liegen von den Gitterpunkten mit keine drei auf einer Geraden. Nach dem Satz von Pick besitzt daher jedes von ihnen aufgespannte Dreieck einen Flächeninhalt von mindestens . Skaliert man das -Gitter auf das Einheitsquadrat, so folgt . Für zusammengesetzte liefert eine Primzahl in der Nähe von dieselbe Schranke. Dieselben Punktmengen sind zugleich Lösungen des No-Three-in-Line-Problems.

1982 widerlegten János Komlós, János Pintz und Endre Szemerédi die Vermutung. Mit der probabilistischen Methode wiesen sie Punktmengen nach, deren kleinstes Dreieck größer ausfällt als bei der Konstruktion von Erdős. Daraus folgt

Der Beweis ist nicht konstruktiv. Claudia Bertram-Kretzberg, Thomas Hofmeister und Hanno Lefmann gaben im Jahr 2000 ein Verfahren an, das Konfigurationen dieser Güte in Polynomialzeit liefert.

Obere Schranken

Eine einfache Überlegung liefert . Zerlegt man die konvexe Hülle der Punkte in Dreiecke mit paarweise disjunktem Inneren, so entstehen mindestens Dreiecke mit Gesamtflächeninhalt höchstens eins, von denen folglich eines höchstens den Flächeninhalt hat.

Die erste nichttriviale Schranke bewies Klaus Friedrich Roth 1951 mit

Nach weiteren Verbesserungen durch Wolfgang M. Schmidt und Roth erreichten Komlós, Pintz und Szemerédi 1981

für eine Konstante . Diese Schranke blieb mehr als vier Jahrzehnte lang unübertroffen. 2023 verbesserten Alex Cohen, Cosmin Pohoata und Dmitrii Zakharov sie auf . Dieselben Autoren erhielten 2025 als Folgerung aus einem Resultat der Inzidenzgeometrie die derzeit beste bekannte Schranke

Exakte Werte für Konfigurationen mit wenigen Punkten

Einheitsquadrat

Michael Goldberg untersuchte 1972 optimale Anordnungen für . Seine Konfigurationen für bis zu sechs Punkte liegen auf dem Rand des Quadrats und sind affine Bilder regelmäßiger Vielecke. Für größere verbesserten Francesc Comellas und J. Luis A. Yebra 2002 diese Werte mittels Simulated Annealing und anschließender analytischer Verfeinerung. In den dabei gefundenen Konfigurationen liegen auch Punkte im Inneren des Quadrats.

Als optimal nachgewiesen sind die Werte bis . Es ist . Zhenbing Zeng und Liangyu Chen wiesen 2011 die Optimalität der Konfiguration von Comellas und Yebra für sieben Punkte nach, mit . Dazu zerlegten sie den Konfigurationsraum rechnergestützt in 226 Teilprobleme und behandelten diese mit Methoden der nichtlinearen Optimierung sowie der Computeralgebra. Lydia Dehbi und Zeng bewiesen 2022

Für ermittelten Chen, Yaochen Xu und Zeng 2017 mit umfangreichen Rechnungen auf CPU- und GPU-Clustern scharfe Schranken.

Konfigurationen, die innerhalb einer numerischen Toleranz global optimal sind, berechneten Amirhossein Monji, Amirali Modir und Burak Kocuk 2025 für mit Methoden der gemischt-ganzzahligen nichtlinearen Optimierung. Nathan Sudermann-Merx verfeinerte diese 2026 analytisch zu exakten Koordinaten und bestätigte damit die Konfigurationen von Comellas und Yebra.

Dreieck

Ist der Bereich ein Dreieck vom Flächeninhalt eins, so sind die exakten Werte für kleine Konfigurationen bekannt. Es gilt sowie , letzteres 1989 von Royce Peng bewiesen. Lu Yang, Jing-Zhong Zhang und Zhenbing Zeng bewiesen 1994 . Zeng und Chen zeigten 2019 und darüber hinaus die Eindeutigkeit der optimalen Konfiguration, mittels einer symbolischen Analyse von acht Fällen.

Für acht Punkte gaben Chen, Zeng und Wenju Zhou 2014 die obere Schranke an. Nathan Sudermann-Merx berechnete 2026 mit einem gemischt-ganzzahligen Optimierungsmodell numerisch eine global optimale Konfiguration für acht Punkte mit und stützt damit diese Schranke.

Konvexe Bereiche

Darf der Bereich mitgewählt werden, so fragt man nach demjenigen konvexen Bereich vom Flächeninhalt eins, für den maximal wird. Andreas Dress, Yang und Zeng zeigten 1995, dass unter je sechs Punkten in einem konvexen Bereich stets ein Dreieck vom Flächeninhalt höchstens des Flächeninhalts von vorkommt und dass nicht verbessert werden kann. Angenommen wird das Maximum vom regelmäßigen Sechseck, mit den sechs Punkten in dessen Ecken. Yang und Zeng behandelten im selben Band den Fall von sieben Punkten und erhielten den Wert . Für alle übrigen Punktzahlen ist dieser Fall ungeklärt. Numerisch bestimmte Konfigurationen ohne Optimalitätsnachweis sind für größere dokumentiert.

Weblinks

Erich's Packing Center von Erich Friedman, mit den besten bekannten Konfigurationen für kleine in Quadrat, Kreis, gleichseitigem Dreieck und konvexen Bereichen

Einzelnachweise

Kategorie:Ungelöstes Problem der Mathematik Kategorie:Kombinatorik Kategorie:Dreieck