Wybieranie najbardziej rozproszonych punktów z zestawu punktów

Czy istnieje (skuteczny) algorytm do wybierania podzbioru punktów z zestawu punktów ( ) tak, aby „obejmowały” większość obszaru (we wszystkich możliwych podzbiorach rozmiaru )?$M$$N$$M < N$$M$

Zakładam, że punkty są w płaszczyźnie 2D.

Naiwny algorytm jest prosty, ale zbyt skomplikowany pod względem złożoności czasowej:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

Szukam bardziej wydajnej lub nawet przybliżonej metody.

Przykład, oto płaszczyzna z kilkoma losowymi punktami:

Dla oczekuję wybrania takich punktów:$M=5$

Zwróć uwagę, że wybrane punkty (czerwone) są rozrzucone po całej płaszczyźnie.

Znalazłem artykuł „ EFEKTYWNIE WYBIERAJĄCY KLUCZOWE PUNKTY DYSTRYBUCJI PRZESTRZENNEJ ”, który jest związany z tym problemem. Zakłada się jednak, że punkty są ważone.

Oto przybliżone rozwiązanie. Ponieważ N jest tak duży, a M jest tak mały, co powiesz na:

1. Oblicz wypukły kadłub N
2. Wybierz maksymalnie M punktów z kadłuba, które spełniają kryteria maksymalnej odległości.
3. Jeśli krok 2 pozostawia mniej niż M punktów, wybierz 1 punkt z wnętrza, który maksymalizuje odległość od wcześniej wybranych punktów.
4. Powtarzaj krok 3, aż liczba wybranych punktów wyniesie M.

Intuicja za tym stoi, ponieważ skoro N >> M i chcesz punktów jak najdalej od siebie, prawdopodobnie będą one blisko krawędzi danych, więc równie dobrze możesz zacząć od kadłuba, a następnie iteracyjnie stamtąd wejdź do środka.

Ponadto, zaczynając od kadłuba, zmniejszasz początkowe wyszukiwanie z N do N ^1/2 .

AKTUALIZACJA

Jeśli kroki 3 i 4 powyżej trwają zbyt długo (ponieważ testujesz iteracyjnie wnętrze zestawu danych), przyszło mi do głowy jeszcze dwa pomysły, aby przyspieszyć twój problem.

1. Wyszukiwanie losowe : Powiedzmy, że w kroku 2 znalazłeś punkty P na kadłubie. Następnie losowo narysuj punkty M - P z wnętrza. Wybierz najlepszy zestaw po X próbach.
2. Symulowane wyżarzanie : oblicz najmniejszą ramkę ograniczającą, która pokrywa twój zestaw danych (nie musi być wyrównany z osiami, może być przechylany). Następnie zdefiniuj zestaw M równomiernie rozmieszczonych punktów siatki na tej obwiedni. Uwaga: punkty te niekoniecznie pokrywają się z żadnym z punktów zestawu danych. Następnie dla każdego punktu siatki znaleźć k -nearest sąsiadów w swoim zbiorze. Uruchom każdą kombinację M x k i wybierz tę, która spełnia kryteria maksymalnego dystansu. Innymi słowy, używasz początkowej siatki jako paska startowego, aby znaleźć dobre początkowe rozwiązanie.

$N$$M$

$M$$M$

$M$$1$$M=3,4,5$

$M=3$$1$$M=4$$M=5$$1$

Jeśli chcemy uniknąć przeważającego wyboru punktów na peryferiach, przydatny może okazać się inny cel. Takim kryterium jest maksymalizacja minimalnej odległości między punktami. Powiązane problemy zostały poruszone w StackOverflow , Computer Science SE , Math.SE i MathOverflow .

$M$$D$$M$$D$

OK, więc chcesz wybrać M punktów z danego zestawu N punktów na płaszczyźnie euklidesowej, aby suma odległości par wybranych punktów była maksymalna, prawda?

Standardowy algorytm wyszukiwania lokalnego jest dość szybki i zapewnia całkiem dobre przybliżenie. Czas działania jest liniowy w N i kwadratowy w M. Jego współczynnik aproksymacji wynosi 1 - 4 / M. Oznacza to, że stosunek ten rośnie wraz ze wzrostem M. Na przykład dla M = 10 dostaje 60% wartości optymalnej, a dla M = 50 dostaje 92% wartości optymalnej.

Algorytm działa również dla przestrzeni euklidesowych o wymiarze ogólnym. W tym przypadku problem jest trudny NP. Ale w samolocie nie wiadomo, czy jest NP-twardy.

Źródłem jest ten artykuł . Mam nadzieję że to pomoże! Pozdrawiam, Alfonso

Jednym z rozwiązań jest:

• $O(n)$

• Spraw, aby M sztucznie rozłożył nawet punkty wewnątrz tego ograniczającego prostokąta, niektóre M są trudniejsze niż inne. W twoim przypadku cztery w rogach prostokąta i jeden w środku

• $O(n(log(n)))$

• $O(m(log(n)))$

$O(n(log(n)))$$\sqrt{M} \in \mathbb{N}$