Największa pusta kula lub prostokąt

Question

W wymiarach N (~ 500), chciałbym znaleźć największą kulę lub prostokąt, tak aby sfera/prostokąt nie zawierał już istniejących punktów. Cały zestaw punktów jest ograniczony prostopadłościennym prostokątem (dolna i górna granica wartości).

Czy istnieje znana metoda/kod czasu wielomianowego, z którego mogę skorzystać w celu rozwiązania mojego problemu?

Dwa dobrze znane algorytmy: i) największy pusty prostokąt w obrębie prostokąta (http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf) oraz ii) znalezienie największego pustego okręgu w obrębie ograniczeń lokalizacji (http://www.cs.dartmouth.edu/reports/TR86-130.pdf) nie działa.

Chociaż złożoność powyższych algorytmów to N log N lub N^2 log N, gdzie N jest liczbą już istniejących punktów, złożoność jest również funkcją liniową liczby wierzchołków wypukłego kadłuba lub obwiedni wielokąt. Prostokąt w 500 wymiarach będzie miał 2^500 narożników, co uniemożliwia zastosowanie powyższych technik.

Idealnie, szukam metody (nie musi to być dokładne), która może określić największy cykl/prostokąt w czasie wielomianu w N (liczba punktów) i D (wymiar).

Dziękuję.

Answer 1

Jednym z możliwych rozwiązań heurystycznych jest ograniczenie dużego prostokąta, tak aby był wyrównany względem osi. W takim przypadku prostokąt może być ograniczony najwyżej 2 * d punktami, gdzie każdy punkt reprezentuje ograniczenie lub maksimum do jednego lub więcej wymiarów. Można wtedy określić, czy punkt znajduje się w tym prostokącie tylko w O (d).

Metoda heurystyczna do tego służy do wyboru 2 punktów i użycia ich do utworzenia początkowego pola granicznego, a następnie losowego dodawania punktów. Jeśli punkt znajduje się wewnątrz pudełka, zmniejsz go lub podziel. Jeśli punkt znajduje się poza polem, spróbuj powiększyć pole. Pojedyncze przejście powinno zająć O (d * N), jeśli pole jest zmniejszone zamiast podziału.

Jakość może być nieco poprawiona przez zapewnienie, że żaden punkt nie znajduje się w obwiedni utworzonej przez dwa punkty. Idealnie byłoby znaleźć wszystkie pary punktów, tak aby żaden punkt nie znajdował się w obwiedni, ponieważ po przekonwertowaniu na wykres powinny pomóc w rozszerzeniu rozwiązania w mniej losowy sposób. Dynamiczne programowanie prawdopodobnie prowadzi do algorytmu, który jest lepszy niż O (d * N^3), być może O (d * N^2) lub lepszy.