Datenstruktur - Durchmesser des Polygon

Question

Ich brauche eine Daten structute die

• addPoint (x, y) in O (log N)
• printDiameter() in O (log N)

ermöglicht Wobei N die aktuelle Anzahl der Punkte im Polygon ist.
Offensichtlich liegen die beiden Punkte auf der konvexen Hülle des Polygons. Mit dem Konzept der Anti-Nodal-Paare (Rotating-Calliper) können wir feststellen, dass der Durchmesser von N Punkten O (N) ist.
This erklärt sauber die O (n) -Lösung, aber es unterstützt nicht das Einfügen von Punkt.

Answer 1

Ein k-d-Baum könnte Insertion in O (logN) tun, solange es in irgendeiner Weise balanced ist. Für den Durchmesser-Teil müssten Sie jeden Knoten überprüfen, um den am weitesten entfernten zu finden, also sollte es O (N) sein. Eine andere Lösung wäre, einen QuadTree zu verwenden und ihn zu durchlaufen, um nur die Knoten zu erhalten, die sich am äußeren Teil des Baums befinden.