Najdalsze pierwsze przejście

Pierwsze pięć punktów w najdalszym pierwszym przejściu płaskiego zestawu punktów. Pierwszy punkt jest wybierany arbitralnie, a każdy kolejny punkt jest jak najdalej od wszystkich wcześniej wybranych punktów.

W geometrii obliczeniowej najdalsze pierwsze przejście zwartej przestrzeni metrycznej to sekwencja punktów w przestrzeni, w której pierwszy punkt jest wybierany arbitralnie, a każdy kolejny punkt jest jak najdalej od zbioru wcześniej wybranych punktów. Tę samą koncepcję można również zastosować do skończonego zbioru punktów geometrycznych, ograniczając wybrane punkty do zbioru lub równoważnie, biorąc pod uwagę skończoną przestrzeń metryczną generowaną przez te punkty. W przypadku skończonej przestrzeni metrycznej lub skończonego zbioru punktów geometrycznych wynikowa sekwencja tworzy permutację punktów , znaną również jako permutacja zachłanna .

Każdy przedrostek najdalszego pierwszego przejścia zapewnia zestaw punktów, które są szeroko rozmieszczone i blisko wszystkich pozostałych punktów. Mówiąc dokładniej, żaden inny zestaw równie wielu punktów nie może być oddalony od siebie o więcej niż dwukrotnie i żaden inny zestaw równie wielu punktów nie może być oddalony o mniej niż połowę od najdalszego pozostałego punktu. Częściowo ze względu na te właściwości, przemierzanie najdalszych punktów ma wiele zastosowań, w tym aproksymację problemu komiwojażera i metrycznego problemu k -centrum . Mogą być konstruowane w czasie wielomianowym lub (dla niskowymiarowych przestrzeni euklidesowych ) aproksymowane w czasie prawie liniowym .

Definicja i właściwości

Najdalsze pierwsze przejście to sekwencja punktów w zwartej przestrzeni metrycznej , przy czym każdy punkt pojawia się co najwyżej raz. Jeśli przestrzeń jest skończona, każdy punkt pojawia się dokładnie raz, a przejście jest permutacją wszystkich punktów w przestrzeni. Pierwszym punktem ciągu może być dowolny punkt w przestrzeni. Każdy punkt p po pierwszym musi mieć maksymalną możliwą odległość do zbioru punktów wcześniejszych niż p w sekwencji, gdzie odległość od punktu do zbioru jest zdefiniowana jako minimalna odległość parami do punktów w zbiorze. Dana przestrzeń może mieć wiele różnych przebiegów od najdalszego pierwszego, w zależności zarówno od wyboru pierwszego punktu w sekwencji (którym może być dowolny punkt w przestrzeni), jak i od powiązań dla maksymalnej odległości między późniejszymi wyborami.

Przejścia w najdalszych punktach mogą charakteryzować się następującymi właściwościami. Ustal liczbę k i rozważ przedrostek utworzony przez pierwsze k punktów najdalszego pierwszego przejścia dowolnej przestrzeni metrycznej. Niech r będzie odległością między końcowym punktem przedrostka a pozostałymi punktami przedrostka. Wtedy ten podzbiór ma następujące dwie właściwości:

• Wszystkie pary wybranych punktów znajdują się w odległości co najmniej r od siebie i
• Wszystkie punkty przestrzeni metrycznej znajdują się w odległości co najwyżej r od podzbioru.

I odwrotnie, każda sekwencja mająca te właściwości, dla wszystkich wyborów k , musi być najdalszym pierwszym przejściem. Są to dwie definiujące właściwości zbioru Delone'a , więc każdy przedrostek najdalszego pierwszego przejścia tworzy zbiór Delone'a.

Aplikacje

Rosenkrantz, Stearns i Lewis (1977) wykorzystali najdalsze pierwsze przejście do zdefiniowania heurystyki najdalszego wstawiania dla problemu komiwojażera . Ta heurystyka znajduje przybliżone rozwiązania problemu komiwojażera, budując trasę na podzbiorze punktów, dodając po jednym punkcie na raz do trasy w kolejności określonej przez najdalsze pierwsze przejście. Aby dodać każdy punkt do trasy, jedna krawędź poprzedniej trasy jest przerywana i zastępowana parą krawędzi przechodzących przez dodany punkt, w najtańszy możliwy sposób. Chociaż Rosenkrantz i in. udowodnić tylko logarytmiczny współczynnik przybliżenia dla tej metody, pokazują, że w praktyce często działa ona lepiej niż inne metody wstawiania z lepszymi możliwymi do udowodnienia współczynnikami przybliżenia.

Później ta sama sekwencja punktów została spopularyzowana przez Gonzaleza (1985) , który wykorzystał ją jako część algorytmów zachłannej aproksymacji dla dwóch problemów w grupowaniu, w których celem jest podzielenie zbioru punktów na k klastrów. Jeden z dwóch problemów, które Gonzalez rozwiązał w ten sposób, ma na celu zminimalizowanie maksymalnej średnicy klastra, podczas gdy drugi, znany jako metryczny problem k -centrum , ma na celu zminimalizowanie maksymalnego promienia, odległości od wybranego centralnego punktu gromady. klaster do najdalszego od niego punktu w tym samym klastrze. Na przykład k -centrum można wykorzystać do modelowania rozmieszczenia remiz strażackich w mieście, aby upewnić się, że wóz strażacki może szybko dotrzeć pod każdy adres w mieście. W przypadku obu problemów z grupowaniem Gonzalez wybiera zestaw k centrów klastrów, wybierając pierwsze k punktów najdalszego pierwszego przejścia, a następnie tworzy klastry, przypisując każdy punkt wejściowy do najbliższego środka klastra. Jeżeli r jest odległością od zbioru k wybranych środków do następnego punktu na pozycji k + 1 w przejściu, to przy tym skupieniu każdy punkt znajduje się w odległości r od swojego środka i każde skupienie ma średnicę co najwyżej 2 r . Jednak podzbiór k centrów wraz z następnym punktem znajdują się w odległości co najmniej r od siebie, a każde k -grupowanie spowodowałoby umieszczenie dwóch z tych punktów w jednym skupieniu, z jednym z nich w odległości co najmniej r / 2 od jej środka io średnicy co najmniej r . Zatem heurystyka Gonzaleza daje współczynnik aproksymacji równy 2 dla obu problemów grupowania.

Heurystyka Gonzaleza została niezależnie ponownie odkryta dla metrycznego problemu k -centrum przez Dyera i Frieze'a (1985) , którzy zastosowali ją bardziej ogólnie do ważonych problemów k -centrum. Inna praca dotycząca problemu k -centrum z tego samego czasu, Hochbaum i Shmoys (1985) , osiąga ten sam współczynnik przybliżenia równy 2, ale jej techniki są inne. Niemniej jednak heurystyka Gonzaleza i nazwa „najdalsze pierwsze przejście” są często błędnie przypisywane Hochbaumowi i Shmoysowi. Zarówno w przypadku problemu grupowania średnic min-max, jak i problemu metrycznego k , te przybliżenia są optymalne: istnienie heurystyki czasu wielomianowego z jakimkolwiek stałym współczynnikiem aproksymacji mniejszym niż 2 oznaczałoby, że P = NP .

Podobnie jak w przypadku grupowania, najdalsze przejście w pierwszej kolejności może być również użyte w innym typie problemu lokalizacji obiektu, problemie rozproszenia obiektu maks-min, w którym celem jest wybranie lokalizacji k różnych obiektów tak, aby były jak najdalej jak najdalej od siebie. Dokładniej, celem tego problemu jest wybranie k punktów z danej przestrzeni metrycznej lub danego zestawu kandydujących punktów w taki sposób, aby zmaksymalizować minimalną odległość parami między wybranymi punktami. Ponownie, można to przybliżyć, wybierając pierwsze k punktów najdalszego pierwszego przejścia. Jeżeli r oznacza odległość k -tego punktu od wszystkich poprzednich punktów, to każdy punkt przestrzeni metrycznej lub zbioru kandydującego znajduje się w odległości r od pierwszych k − 1 punktów. Zgodnie z zasadą przegródki , jakieś dwa punkty rozwiązania optymalnego (cokolwiek to jest) muszą znajdować się w odległości r od tego samego punktu wśród tych pierwszych k - 1 wybranych punktów i (zgodnie z nierównością trójkąta ) w odległości 2 r od siebie . Dlatego rozwiązanie heurystyczne podane przez najdalsze pierwsze przejście mieści się w zakresie współczynnika optymalnego wynoszącym dwa razy.

Inne zastosowania najdalszego pierwszego przejścia obejmują kwantyzację kolorów (grupowanie kolorów na obrazie do mniejszego zestawu reprezentatywnych kolorów), progresywne skanowanie obrazów (wybór kolejności wyświetlania pikseli obrazu , tak aby prefiksy kolejności dawały dobre wersje całego obrazu o niższej rozdzielczości zamiast wypełniania obrazu od góry do dołu), selekcja punktów w metodzie probabilistycznej mapy drogowej do planowania ruchu , uproszczenie chmur punktów , generowanie masek dla obrazów rastrowych , grupowanie hierarchiczne , znajdowanie podobieństw między wielokątami siatki o podobnych powierzchniach, wybieranie różnorodnych i wartościowych celów obserwacyjnych do podwodnej eksploracji robotów, wykrywanie uszkodzeń w sieciach sensorowych , modelowanie różnorodności filogenetycznej , dopasowywanie pojazdów w heterogenicznej flocie do zleceń dostaw klientów, równomierne rozmieszczenie obserwatoriów geodezyjnych na powierzchni Ziemi lub inne typy sieci sensorowych, generowanie wirtualnych świateł punktowych w metodzie natychmiastowego renderowania grafiki komputerowej radiosity oraz struktury danych przeszukiwania zasięgu geometrycznego .

Algorytmy

Chciwy dokładny algorytm

Najdalsze pierwsze przejście skończonego zbioru punktów można obliczyć za pomocą zachłannego algorytmu , który utrzymuje odległość każdego punktu od poprzednio wybranych punktów, wykonując następujące kroki:

• Zainicjuj sekwencję wybranych punktów do sekwencji pustej, a odległości każdego punktu do wybranych punktów do nieskończoności.
• Chociaż nie wszystkie punkty zostały wybrane, powtórz następujące kroki:
  • Przejrzyj listę jeszcze nie wybranych punktów, aby znaleźć punkt p , który ma maksymalną odległość od wybranych punktów.
  • Usuń p z jeszcze nie wybranych punktów i dodaj je na końcu sekwencji wybranych punktów.
  • Dla każdego pozostałego, jeszcze nie wybranego punktu q , zamień odległość zapisaną dla q na minimum jego starej wartości i odległość od p do q .

Dla zbioru n punktów ten algorytm wykonuje O ( n ² ) kroków i O ( n ² ) obliczeń odległości.

przybliżenia

szybszej aproksymacji , podany przez Har-Peleda i Mendela (2006) , ma zastosowanie do dowolnego podzbioru punktów w przestrzeni metrycznej z ograniczonym wymiarem podwajania , klasy przestrzeni, która obejmuje przestrzenie euklidesowe o ograniczonym wymiarze. Ich algorytm znajduje ciąg punktów, w których każdy kolejny punkt ma odległość w zakresie 1 - ε największej odległości od poprzednio wybranego punktu, gdzie ε można wybrać jako dowolną liczbę dodatnią. To wymaga czasu ${\ Displaystyle O (n \ log n)}$ .

Wyniki dla ograniczonego wymiaru podwojenia nie mają zastosowania do wielowymiarowych przestrzeni euklidesowych, ponieważ stały czynnik w notacji dużego O dla tych algorytmów zależy od wymiaru. Zamiast tego inna metoda aproksymacji oparta na lemacie Johnsona-Lindenstraussa i mieszaniu wrażliwym na lokalizację ma czas działania ${\ Displaystyle O (\ varepsilon ^ {- 2} n ^ {1 + 1/(1 + \ varepsilon) ^ {2} + o (1)}).} Dla metryk zdefiniowanych przez najkrótsze ścieżki na ważonych wykresach$ niekierowanych , a losowa konstrukcja przyrostowa oparta na algorytmie Dijkstry osiąga czas ${\ Displaystyle O (\ varepsilon ^ {- 1} m \ log n \ log {\ tfrac {n} {\ varepsilon }})}$ , gdzie n i m to odpowiednio liczby wierzchołków i krawędzi grafu wejściowego.

Przyrostowe wstawienie Woronoja

W przypadku wybierania punktów z ciągłej przestrzeni, takiej jak płaszczyzna euklidesowa , a nie ze skończonego zbioru kandydujących punktów, metody te nie będą działać bezpośrednio, ponieważ do utrzymania byłaby nieskończona liczba odległości. Zamiast tego każdy nowy punkt powinien być wybrany jako środek największego pustego okręgu zdefiniowanego przez poprzednio wybrany zbiór punktów. Centrum to zawsze będzie leżeć na wierzchołku diagramu Woronoja z już wybranych punktów lub w punkcie, w którym krawędź diagramu Woronoja przecina granicę dziedziny. W tym sformułowaniu metoda konstruowania najdalszych pierwszych przejść została również nazwana przyrostowym wstawieniem Woronoja . Jest podobny do udoskonalania Delaunaya dla generowania siatki elementów skończonych , ale różni się wyborem wierzchołka Voronoi do wstawienia na każdym kroku.

Zobacz też

• Algorytm Lloyda , inna metoda generowania równomiernie rozmieszczonych punktów w przestrzeniach geometrycznych