Zum Inhalt
Anmelden
Alle Apps

Halbierende Geraden

Über diese App

n Punkte in der Ebene: Wie viele Geraden durch zwei von ihnen teilen die übrigen genau in zwei Hälften? Punkte setzen und ziehen, alle Halbierenden leuchten live; Lovász' rotierende Gerade zählt sie als Wechsel; Rekordmengen aus einer Suche; Log-log-Diagramm gegen Deys n^{4/3}. Neu: höchstens C·n^{4/3−ε}, openai/math Familie 183 (Lean-formalisiert).

Worum es geht

Nimm n Punkte in der Ebene, keine drei auf einer Geraden, n gerade. Eine Gerade durch zwei der Punkte heißt halbierend, wenn auf jeder Seite genau (n−2)/2 der übrigen liegen. Wie viele halbierende Geraden kann eine Punktmenge höchstens haben? Die Frage gehört zum k-Mengen-Problem der algorithmischen Geometrie. Mindestens n/2 sind es immer; nach oben drückte Tamal Dey 1998 die Schranke auf n^(4/3), seither stand der Exponent. Die besten Konstruktionen liegen weit darunter, bei n·e^(c√log n). Ein KI-erzeugtes Preprint aus github.com/openai/math (Familie 183) zeigt nach eigener Darstellung höchstens C·n^(4/3−ε) mit nicht bezifferten Konstanten. Laut Katalog ist der Hauptsatz in Lean formalisiert, begutachtet ist das Preprint nicht.

Was die App zeigt

Du setzt und ziehst Punkte, und alle halbierenden Geraden leuchten live. Vorlagen bieten konvexe Lage mit genau n/2 Halbierenden, Zufall und Rekordmengen aus einer langen Suche. Eine rotierende Gerade zeigt die Sicht von Lovász: In jeder Richtung gibt es eine Gerade, die die Punkte halbiert, und beim Drehen wechselt sie ihr Punktepaar genau an den Halbierenden. Ein Log-log-Diagramm vergleicht deine Werte mit n/2, n^(4/3) und n^(3/2). Für die neue Schranke zeichnet die App keine Kurve, weil der Beweis keine Zahlenwerte nennt.

Selbst ausprobieren

Beginne mit der konvexen Lage und ziehe einzelne Punkte ins Innere: Die Zahl der Halbierenden steigt. Lass die Suche laufen, die Punkte verschiebt und jede Verbesserung behält. Starte die rotierende Gerade und zähle mit, wie oft sie bei einer halben Umdrehung ihr Paar wechselt. Bei ungerader Punktzahl gibt es keine halbierenden Paare. Wie schnell solche Zahlen mit n wachsen können, entscheidet keine Suche; das leistet nur der Beweis.

Häufige Fragen

Was ist eine halbierende Gerade?
Bei n Punkten in allgemeiner Lage (n gerade) ist eine halbierende Gerade eine Gerade durch zwei der Punkte, die die übrigen n−2 Punkte in zwei gleich große Hälften teilt. Ihre Anzahl hängt von der Lage der Punkte ab. In konvexer Lage sind es genau n/2.
Was ist das k-Mengen-Problem?
Eine k-Menge ist eine Teilmenge von k Punkten, die sich durch eine Gerade vom Rest abtrennen lässt. Das k-Mengen-Problem fragt, wie viele solche Teilmengen eine Menge von n Punkten höchstens haben kann. Die halbierenden Geraden entsprechen dem Fall k ≈ n/2 und sind der schwierigste Kern des Problems.
Ist Deys Schranke n^(4/3) für halbierende Geraden verbessert?
Ein KI-erzeugtes Preprint aus dem Katalog github.com/openai/math (Familie 183) zeigt nach eigener Darstellung, dass jede hinreichend große Menge höchstens C·n^(4/3−ε) halbierende Geraden hat, mit absoluten, aber nicht bezifferten Konstanten. Laut Katalog ist der Hauptsatz in Lean formalisiert. Das Preprint ist noch nicht begutachtet, und die Lücke zur besten Konstruktion bleibt groß.
Was kann ich in dieser App ausprobieren?
Du setzt, ziehst und entfernst Punkte und siehst alle halbierenden Geraden live. Eine rotierende Gerade zählt sie als Wechsel, eine Suche findet Punktmengen mit vielen Halbierenden. Ein Diagramm vergleicht deine Werte mit den bekannten Schranken.

Fach: Offene Probleme, gelöst von KI

Mehr aus Offene Probleme, gelöst von KI

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps