Znalezienie największego zestawu punktów o ograniczonej średnicy

Biorąc pod uwagę punkty w i odległość znajduję największy podzbiór tych punktów, tak że odległość euklidesowa nie jest większa niż . $p_1,\ldots,p_n$ $\mathbb{R}^{d}$ $l$ $l$

Jaka jest złożoność tego problemu?

Na wykresie nad punktami, które mają krawędź, ilekroć odległość dwóch punktów wynosi co najwyżej , problem jest równoznaczny ze znalezieniem maksymalnej kliki. Odwrotność może się nie utrzymywać, ponieważ nie każdy wykres można uzyskać w ten sposób (przykładem jest gwiazda dla ). Dlatego powiązane pytanie brzmi: co wiadomo o tej klasie grafów? $l$ $K_{1,7}$ $d=2$

ds.algorithms reference-request cg.comp-geom

— Marcus Ritt
źródło

Zauważ, że jeśli jest ustalone, istnieje „trywialny” algorytm czasu P: ponieważ taki zestaw jest zamknięty w kulce o promieniu i bez utraty ogólności piłka jest minimalna (tzn. Dotyka punktów), wystarczy wyliczyć wszystkie podzbiory. Możesz zrobić lepiej, ale ze złożonego punktu widzenia problem jest „łatwy”.

d

$d$

l / 2

$l/2$

d + 1

$d+1$

— Suresh Venkat,

Nie sądzę, że to prawda, że optymalny zestaw jest koniecznie zamknięty w kuli o promieniu l / 2. Na przykład w płaszczyźnie trzy wierzchołki równobocznego trójkąta o długości boku 1 nie są tak zamknięte.

— David Eppstein,

ah prawda. ale wyliczenie powinno działać niezależnie.

— Suresh Venkat,

Możesz wyliczyć podzbiory wewnątrz kulek, ale jeśli zrobisz promień l / 2, nie znajdziesz żadnych podzbiorów o małej średnicy, a jeśli zwiększysz promień, to nie jest oczywiste, jak przyciąć podzbiory, aby były mają niską średnicę.

— David Eppstein,

dlaczego nie mogę wyliczyć podzbiorów, znaleźć min kuli otaczającej i obliczyć liczność wewnątrz każdego z nich?

— Suresh Venkat,

Odpowiedzi:

W moim artykule z Jeffem Ericksonem jest „Algorytm czasowy dla dwuwymiarowej wersji tego problemu,„ Iteracja najbliższych sąsiadów i znajdowanie minimalnych polytopów ”, Disc. Komp. Geom. 11: 321–350, 1994. W rzeczywistości gazeta przede wszystkim analizuje podwójny problem: biorąc pod uwagę liczbę punktów w podzbiorze, znajdź najmniejszą możliwą średnicę; ale wykorzystuje problem opisany jako podprogram. Przynajmniej w chwili, gdy to pisaliśmy, nie znaliśmy niczego podwykładniczego dla wyższych wymiarów (chociaż jeśli podzbiór ma w sobie tylko punkty część wykładnicza może być uzależniona od zamiast przy użyciu technik z tego samego artykułu). $O(n^3\log n)$ $k$ $k$ $n$

— David Eppstein
źródło

Przybliżenie jest dość łatwe, jeśli interesuje Cię najmniejszy podzbiór o średnicy co najwyżej . Algorytm czasu liniowego z wykorzystaniem siatek jest już „standardowy”. Stała prawdopodobnie byłaby czymś w rodzaju . $(1+\epsilon)l$ $2^{O(1/\epsilon^d)}$

Trochę pracy nad znalezieniem najmniejszej piłki zawierającej k punktów, ale problem średnicy jest z natury trudniejszy. Aby zobaczyć, dlaczego dobrym punktem wyjścia jest papier Clarkson-Shor do obliczania średnicy w 3d.

BTW, w przypadku dużych wymiarów problem z kulą jest przybliżony pod względem wykładniczym w czasie w (lub innym podobnym hałasie), przy użyciu zestawów rdzeniowych (ale nie w wymiarze!). Wątpię, czy to podejście można rozszerzyć na ten problem, ale mogę się mylić. $O(1/\epsilon^2)$

— Sariel Har-Peled
źródło