Wybieranie najbardziej rozproszonych punktów z zestawu punktów

15

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:

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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.

optimization computational-geometry

— Libor
źródło

2

W przypadku zobacz to z StackOverflow: Algorytm znajdujący punkty, które są najdalej od siebie - lepsze niż O (n ^ 2)? .

M = 2

$M=2$

— hardmath

Niestety, wynosi zwykle około 1500-5000, a około 10-50.

N

$N$

M

$M$

— Libor

Czy oba i są stałe, czy też zmieniasz (np. Ponieważ chcesz zmaksymalizować średnią odległości, w którym to przypadku zwiększenie może spowodować zmniejszenie)?

M

$M$

N

$N$

M

$M$

M

$M$

— Wolfgang Bangerth

1

Podejrzewam, że to trudne NP. Przypomina to problem kliki o maksymalnej masie, gdzie ciężar krawędzi między dwoma wierzchołkami jest odległością euklidesową między nimi. (Wierzę, że istnieją praktycznie skuteczne heurystyki znane z max-clique. Nie jestem pewien, które to są.)

— tmyklebu

1

@hardmath Przepraszamy, to była literówka. Próbowałem zilustrować, co muszę osiągnąć. Problem pochodzi z ekstrakcji cech obrazu, w której muszę uzyskać tylko garść cech punktowych, ale rozproszenie ich po całym obrazie, ponieważ są one używane do oszacowania transformacji, a gdy są rozproszone przestrzennie, oszacowanie jest bardziej stabilne. Może lepszym rozwiązaniem jest „entropia” - chciałbym wybrać

punktów tak, aby były wszędzie, jak gaz w stanie maksymalnej entropii. Z drugiej strony staram się unikać grupowania wybranych punktów.

M

$M$

— Libor

11

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

Oblicz wypukły kadłub N
Wybierz maksymalnie M punktów z kadłuba, które spełniają kryteria maksymalnej odległości.
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.
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.

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.
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.

— dpmcmlxxvi
źródło

Dzięki. Może źle sformułował pytanie. Dążę do takiego zbioru punktów, aby „obejmowały” większość obszaru. Myślałem, że wystarczy kryterium odległości, ale wygląda na to, że trzeba coś jeszcze dodać.

— Libor

M

$M$

1

Być może bardziej formalnym sposobem stwierdzenia problemu jest to, że chcesz teselacji rozmiaru M, która obejmuje N i minimalizuje średni obszar aspektu teselacji? Minimalizacja obszarów aspektów wydaje się sposobem na rozłożenie punktów wokół i upewnienie się, że się nie zlepią.

— dpmcmlxxvi

Tak. Chciałem uniknąć korzystania z siatki, ponieważ jeśli punkty mogą zostać przypadkowo zgrupowane wokół linii siatki, a następnie zostaną zgrupowane w zaznaczeniu.

— Libor,

Jedyny problem z twoim chciwym algorytmem, o którym wspomniałeś, to to, że będzie on bardzo wrażliwy na początkowy punkt początkowy. Algorytmy uprawy nasion (gdzie zaczynamy od wewnątrz) mają ten problem. Podejście do kadłuba, o którym wspominam, będzie prawdopodobnie bardziej stabilne, ponieważ działa od zewnątrz.

— dpmcmlxxvi

6

$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$

— matematyka
źródło

1

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

— Alfonso
źródło

1

Rozwiązałem to już za pomocą algorytmu „Suppression via Disk Covering” z artykułu „Efektywne wybieranie rozproszonych przestrzennie punktów kluczowych do śledzenia wizualnego” 18. 18. Międzynarodowa Konferencja IEEE na temat przetwarzania obrazu. IEEE, 2011

— Libor

1

Alfonso, proszę wyraźnie podać swoją przynależność do sugerowanego artykułu.

— nicoguaro

0

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}$

— Jan Hackenberg
źródło