größte leere Kugel oder Rechteck

Question

In N (~ 500) Dimensionen möchte ich die größte Kugel oder das Rechteck herausfinden, so dass die Kugel/das Rechteck keine bereits vorhandenen Punkte enthält. Die gesamte Menge von Punkten ist in einer achsgerechten rechteckigen Box (untere und obere Grenze der Werte) begrenzt.

Gibt es eine bekannte polynomielle Zeitmethode/Code, mit der ich mein Problem lösen kann?

Die beiden bekannten Algorithmen: i) das größte leere Rechteck innerhalb eines Rechtecks ​​(http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf) und ii) das Finden des größten leeren Kreises innerhalb von Ortsbedingungen (http://www.cs.dartmouth.edu/reports/TR86-130.pdf) funktioniert nicht.

Obwohl die Komplexität der obigen Algorithmen N log N oder N^2 log N ist, wobei N die Anzahl der bereits vorhandenen Punkte ist, ist die Komplexität auch eine lineare Funktion der Anzahl der Ecken der konvexen Hülle oder der Begrenzung Polygon. Ein Rechteck in 500 Dimensionen wird 2^500 Ecken haben, was die obigen Techniken unmöglich macht.

Idealerweise suche ich nach einer Methode (sie muss nicht exakt sein), die in N (Anzahl der Punkte) und D (der Dimension) den größten Kreis/das größte Rechteck in Polynomialzeit bestimmen kann.

Vielen Dank.

Answer 1

Eine mögliche heuristische Lösung besteht darin, das große Rechteck so einzuschränken, dass es in der Achse ausgerichtet ist. In diesem Fall kann ein Rechteck von höchstens 2 * d Punkten begrenzt werden, wobei jeder Punkt eine Grenze von min oder max zu einer oder mehreren Dimensionen darstellt. Es kann dann bestimmt werden, ob ein Punkt innerhalb dieses Rechtecks ​​nur in O (d) ist.

Eine heuristische Methode, um davon Gebrauch zu machen, besteht darin, zwei Punkte auszuwählen und diese zu verwenden, um eine anfängliche Bounding Box zu bilden und dann nach dem Zufallsprinzip Punkte hinzuzufügen. Wenn der Punkt innerhalb der Box ist, verkleinern oder teilen Sie die Box. Wenn der Punkt außerhalb der Box liegt, versuchen Sie, die Box größer zu machen. Ein einzelner Durchgang sollte O (d * N) annehmen, wenn die Box geschrumpft anstatt gespalten wird.

Die Qualität kann vielleicht etwas verbessert werden, indem sichergestellt wird, dass sich kein Punkt innerhalb der durch die beiden Punkte gebildeten Begrenzungsbox befindet. Es kann ideal sein, alle Punktepaare so zu finden, dass sich kein Punkt innerhalb der Begrenzungsbox befindet, da sie, wenn sie in ein Diagramm konvertiert werden, dazu beitragen, die Lösung auf eine weniger zufällige Weise zu erweitern. Dynamische Programmierung führt wahrscheinlich zu einem Algorithmus, der besser ist als O (d * N^3), vielleicht O (d * N^2) oder besser.