Was ist diese Datenstruktur / dieses Datenkonzept, bei dem ein Punktediagramm eine Aufteilung in einen Raum definiert?

15

Ich bin auf einen Algorithmus gestoßen, um ein Problem der realen Welt zu lösen, und ich erinnere mich an eine Klasse, in der ich für einige etwas sehr Ähnliches für ein Hausaufgabenproblem gemacht habe. es sieht aus wie das

Grundsätzlich handelt es sich um eine Darstellung von Punkten, und die Linien sind so gezeichnet, dass sie zwischen zwei Punkten den gleichen Abstand haben. Es bildet eine perfekte Partition, in der die Linien um den Punkt die Form des Bereichs bilden, der diesem Punkt am nächsten liegt. Läutet das jemandem eine Glocke? Ich hatte eine harte Zeit, Beschreibungen zu googeln und Ergebnisse zu erzielen. Und ich weiß nicht, wie ich es sonst beschreiben soll. Hoffentlich hilft das Bild.

Brian
quelle
1667 Mal gesehen seit gestern? Wird SE gehackt?
HEKTO
@ HEKTO wurde als eine der "Hot Network Questions" angezeigt.
Apass.Jack

Antworten:

31

Was Sie beschrieben, ist Voronoi-Diagramm .

Hier ist ein Auszug aus Wikipedia.

Bild des Voronoi-Diagramms aus Wikipedia

Im einfachsten Fall, wie im ersten Bild gezeigt, erhalten wir eine endliche Menge von Punkten in der euklidischen Ebene. In diesem Fall ist jeder Ort einfach ein Punkt, und seine entsprechende Voronoi-Zelle besteht aus jedem Punkt in der euklidischen Ebene, dessen Abstand zu kleiner oder gleich seinem Abstand zu anderen Punkten ist. Jede solche Zelle ergibt sich aus dem Schnittpunkt der Halbräume und ist daher ein konvexes Polygon. Die Liniensegmente des Voronoi-Diagramms sind alle Punkte in der Ebene, die gleich weit von den beiden nächstgelegenen Standorten entfernt sind. Die Voronoi-Eckpunkte (Knoten) sind die Punkte mit gleichem Abstand zu drei (oder mehr) Stellen.p1,,pnpkRkpk

Apass.Jack
quelle
4
+1. Ich habe darauf verzichtet und mich für Implementierungen entschieden, weil ich mich erinnere, dass meine Professoren sie mit einer Fußnote erwähnt haben, dass die Implementierung von Voronoi-Diagrammen in höheren Dimensionen rechnerisch recht komplex ist. Einfache kNN-Implementierungen erledigen den Job also viel besser. Die Bedingung, dass "Linien mit gleichem Abstand zwischen zwei Punkten gezeichnet werden", kann jedoch möglicherweise nicht erfüllt werden.
Sagnik