Blatt · Nachbarschaft
Nachbarschaft — wer hier am nächsten ist
Streue ein paar Kerne in die Fläche und färbe jeden Punkt nach dem Kern, der ihm am nächsten liegt. Es entsteht eine Aufteilung in Zellen — und ganz von selbst ein zweites Gebilde: das Netz der Kerne, deren Zellen aneinandergrenzen. Beide sind dieselbe Sache von zwei Seiten gesehen. Dieses Blatt baut das Netz, hält es gegen die rohe Frage „wer ist am nächsten?", zählt für kleine Mengen alle Netze auf, die es überhaupt gibt — und zeigt die Stelle, an der Rechnen mit Fließkomma allein ein Netz baut, das keines ist.
Klicken setzt einen Kern, Ziehen verschiebt ihn, Umschalt-Klick nimmt ihn weg.
„Knappheit messen" oben zählt für dreierlei Eingaben aus, wie knapp die Entscheidung „liegt der vierte Punkt im Umkreis?" jeweils ausfällt — und legt daneben, wo der Rundungsfehler anfängt und wo die Schranke an BigInt abgibt.
Zuerst das Netz gegen seine eigene Bedingung — jedes Dreieck gegen jeden Punkt, nicht gegen eine Stichprobe. Dann die Zellen gegen die rohe Frage „welcher Kern ist am nächsten?", an hunderttausenden Rasterpunkten gestellt. Dann für kleine Mengen alle Netze, die es überhaupt gibt, gegen dieses eine. Und zuletzt derselbe Bau ohne exakte Entscheidung — damit sichtbar wird, was sie kostet und was sie einbringt.
noch nicht geprüft
Wo das vorkommt
Einzugsgebiete von Sendemasten, Rettungswachen und Filialen. Kristallkörner in Metall. Gelände aus Höhenpunkten, wo das Netz die Dreiecke liefert, die am wenigsten spitz sind. Und der Klassiker von 1854: John Snow zeichnete um die Londoner Wasserpumpen genau diese Zellen — die Cholera-Toten lagen fast alle in der Zelle einer einzigen Pumpe.
Warum sechs
Ein ebenes Netz aus Dreiecken hat höchstens 3n − 6 Kanten, also im Mittel
weniger als sechs Nachbarn pro Kern — gleich wie gestreut wird. Das ist kein
Erfahrungswert, sondern fällt aus der Eulerschen Formel V − E + F = 2. Der
Prüflauf misst beides an jeder Streuung nach.
Warum hier Fließkomma bricht
„Liegt der Punkt im Umkreis?" ist eine Vorzeichenfrage an einer Determinante. Nahe
null entscheidet der Rundungsfehler statt der Geometrie — und ein einziges falsches
Vorzeichen macht nicht nur ein Dreieck falsch, sondern kann das ganze Netz zerreißen, weil
jeder weitere Schritt darauf aufbaut. Deshalb hier: ganze Koordinaten, schnelle Abschätzung
mit Schranke, und bei Zweifel BigInt.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Alle Blätter: ssims437.github.io