Finden der größten Anzahl von Punkten mit begrenztem Durchmesser

Bei gegebenen Punkten in R d und einem Abstand l ergibt sich die größte Teilmenge dieser Punkte, so dass der euklidische Abstand von keinem von beiden größer als l ist .$p_1,\ldots,p_n$$\mathbb{R}^{d}$$l$$l$

Wie komplex ist dieses Problem?

In der graphischen Darstellung über die Punkte , die eine Kante hat , wenn der Abstand von zwei Punkten höchstens , ist das Problem , äquivalent zu einer maximalen Gruppe zu finden. Die Umkehrung kann möglicherweise nicht gelten, da nicht jeder Graph auf diese Weise erhalten werden kann (ein Beispiel ist der Stern K 1 , 7 für d = 2 ). Daher ist eine verwandte Frage: Was ist über diese Klasse von Graphen bekannt?$l$$K_{1,7}$$d=2$

Es gibt einen -Zeitalgorithmus für die zweidimensionale Version dieses Problems in meinem Artikel mit Jeff Erickson, " Ich habe die nächsten Nachbarn durchlaufen und minimale Polytope gefunden ", Disc. Comp. Geom. 11: 321-350, 1994. Tatsächlich befasst sich der Aufsatz hauptsächlich mit dem doppelten Problem: Finden Sie angesichts der Anzahl der Punkte in der Teilmenge den kleinstmöglichen Durchmesser; Es wird jedoch das von Ihnen als Unterroutine beschriebene Problem verwendet. Zumindest zu dem Zeitpunkt, als wir es geschrieben haben, wussten wir nichts Subexponentielles für höhere Dimensionen (obwohl, wenn die Teilmenge nur k Punkte enthält, der exponentielle Teil eher von k als von n abhängig gemacht werden kann$O(n^3\log n)$$k$$k$$n$ unter Verwendung von Techniken in der gleichen Arbeit).

Annäherung ist ziemlich einfach, wenn Sie an der kleinsten Teilmenge mit einem Durchmesser von höchstens interessiert sind . Ein linearer Zeitalgorithmus unter Verwendung von Gittern ist mittlerweile "Standard". Die Konstante wäre wahrscheinlich so etwas wie 2 O ( 1 / ε d ) .$(1+\epsilon)l$$2^{O(1/\epsilon^d)}$

Es gibt einige Arbeiten, um die kleinste Kugel mit k Punkten zu finden, aber das Durchmesserproblem ist von Natur aus schwieriger. Ein guter Ausgangspunkt ist das Clarkson-Shor-Papier zur Berechnung des Durchmessers in 3d.

Übrigens ist das Kugelproblem für große Dimensionen in (oder einem ähnlichen Rauschen) mit Hilfe von Kernsätzen (aber nicht in der Dimension!) Zeitlich exponentiell approximierbar. Ich bezweifle, dass dieser Ansatz auf dieses Problem ausgeweitet werden kann, aber ich könnte mich irren. $O(1/\epsilon^2)$