Partition 2D zeigt in N Regionen mit jeweils K Nachbarpunkten

Question

Wenn man eine Sammlung von Punkten in einem 2D Raum hat, gibt es dann einen Algorithmus, der diese Punkte in N "Regionen" aufteilt, die jeweils K Nachbarpunkte enthalten?

Angenommen, diese 20 Punkte werden in 4 Gruppen zu je 5 Punkten gruppiert. Eine zufriedenstellende Lösung könnte so aussehen:

Motivation: Ich versuche, ein visualization that loads lots of images into the browser zu optimieren. Ich plane, Bilder mit sehr geringer Auflösung beim Laden der Seite zu laden und dann die Auflösung der Bilder in einer Region zu erhöhen, wenn Nutzer diese Region vergrößern. Natürlich muss ich den Platz quantisieren. Wenn Benutzer also direkt in die Mitte des obigen Beispiels scrollen, müsste ich hochauflösende Bilder für jede der 4 Gruppen holen.

console.log('stackoverflow wants code for posts with codepen links') 

Answer 1

Ein Algorithmus kann wie folgt sein:

- get a triangulation of the points (for example: Delaunay Triangulation): D 
- get a planar graph from D: G 
- Then partition G into connected subgraphs with equal size k 

Für den letzten Schritt this solution kurz und einfach ist (von Theoretische Informatik Website):

Compute einen konstanten Grad Spanning Tree T Ihres Graphen, Wurzel es, und jetzt gierig finden Teilbäume von etwa Größe r, extrahieren sie und wiederholen. Wenn es keinen Konstantenbaum gibt, der den konstanten Grad aufweist, dann zeigt das oben gezeigte Sternbeispiel natürlich, dass dieser Algorithmus fehlschlagen kann.