Maksymalny zbiór rozłączny

W geometrii obliczeniowej maksymalny zbiór rozłączny ( MDS ) to największy zbiór nienakładających się kształtów geometrycznych wybranych z danego zestawu kandydujących kształtów.

Każdy zestaw nienakładających się kształtów jest niezależnym zbiorem na wykresie przecięcia kształtów. Dlatego problem MDS jest szczególnym przypadkiem maksymalnego zbioru niezależnego (MIS) . Oba problemy są NP kompletne , ale znalezienie MDS może być łatwiejsze niż znalezienie MIS z dwóch powodów:

W przypadku ogólnego problemu MIS najbardziej znane dokładne algorytmy są wykładnicze. Na niektórych wykresach przecięć geometrycznych istnieją algorytmy podwykładnicze do znajdowania MDS.
Ogólny problem MIS jest trudny do przybliżenia i nie ma nawet przybliżenia ze stałym współczynnikiem. Na niektórych wykresach przecięć geometrycznych istnieją schematy aproksymacji w czasie wielomianowym (PTAS) do znajdowania MDS.

Znalezienie MDS jest ważne w aplikacjach, takich jak automatyczne umieszczanie etykiet , projektowanie obwodów VLSI i multipleksowanie z podziałem częstotliwości komórkowych .

Problem MDS można uogólnić, przypisując każdemu kształtowi inną wagę i szukając zbioru rozłącznego o maksymalnej wadze całkowitej.

W poniższym tekście MDS( C ) oznacza maksymalny zbiór rozłączny w zbiorze C .

Chciwe algorytmy

Biorąc pod uwagę zbiór C kształtów, przybliżenie do MDS( C ) można znaleźć za pomocą następującego algorytmu zachłannego :

INICJALIZACJA: Zainicjuj pusty zestaw, S .
SZUKAJ: Dla każdego kształtu x w C :
1. Oblicz N(x) - podzbiór wszystkich kształtów w C , które przecinają x (w tym sam x ).
2. Oblicz największy niezależny zbiór w tym podzbiorze: MDS(N(x)) .
3. Wybierz x takie, że |MDS(N(x))| jest zminimalizowany.
Dodaj x do S .
Usuń x i N(x) z C .
C są kształty , wróć do wyszukiwania.
KONIEC: zwróć zestaw S .

Dla każdego kształtu x , który dodamy do S , tracimy kształty w N(x) , ponieważ są one przecinane przez x i dlatego nie mogą być później dodane do S . Jednak niektóre z tych kształtów same się przecinają, a zatem w żadnym przypadku nie jest możliwe, aby wszystkie znajdowały się w optymalnym rozwiązaniu MDS(S) . Największym podzbiorem kształtów, które mogą znajdować się w rozwiązaniu optymalnym, jest MDS(N(x)) . Dlatego wybranie x , które minimalizuje |MDS(N(x))| minimalizuje stratę z dodania x do S .

W szczególności, jeśli możemy zagwarantować, że istnieje x , dla którego |MDS(N(x))| jest ograniczony przez stałą (powiedzmy M ), to ten zachłanny algorytm daje stałe przybliżenie współczynnika M , ponieważ możemy zagwarantować, że:

${\ Displaystyle | S | \ geq {\ Frac {| MDS (C) |} {M}}}$

Taka górna granica M istnieje dla kilku interesujących przypadków:

Przedziały jednowymiarowe: dokładny algorytm wielomianowy

Gdy C jest zbiorem przedziałów na linii, M = 1, a zatem algorytm zachłanny znajduje dokładny MDS. Aby to zobaczyć, załóżmy wlog, że przedziały są pionowe i niech x będzie przedziałem z najwyższym dolnym punktem końcowym . Wszystkie inne przedziały przecięte przez x muszą przecinać jego dolny punkt końcowy. Dlatego wszystkie przedziały w N(x) przecinają się ze sobą, a MDS(N(x)) ma rozmiar co najwyżej 1 (patrz rysunek).

Dlatego w przypadku 1-wymiarowym MDS można znaleźć dokładnie w czasie O ( n log n ):

Posortuj przedziały w porządku rosnącym ich dolnych punktów końcowych (zajmuje to czas O ( n log n )).
Dodaj przedział z najwyższym dolnym punktem końcowym i usuń wszystkie przecinające go przedziały.
Kontynuuj, aż nie pozostanie żadna przerwa.

Algorytm ten jest analogiczny do rozwiązania problemu planowania interwałowego dotyczącego najwcześniejszego ostatecznego terminu .

W przeciwieństwie do przypadku 1-wymiarowego, w 2 lub więcej wymiarach problem MDS staje się NP-zupełny, a zatem ma albo dokładne algorytmy super-wielomianowe, albo przybliżone algorytmy wielomianowe.

Kształty tłuszczu: przybliżenia o stałym współczynniku

Kiedy C jest zbiorem dysków jednostkowych, M = 3, ponieważ dysk najbardziej wysunięty na lewo (dysk, którego środek ma najmniejszą współrzędną x ) przecina co najwyżej 3 inne rozłączne dyski (patrz rysunek). Dlatego algorytm zachłanny daje przybliżenie 3, tj. znajduje zbiór rozłączny o rozmiarze co najmniej MDS(C) /3.

Podobnie, gdy C jest zbiorem równoległych do osi kwadratów jednostkowych, M = 2.

Gdy C jest zbiorem dysków o dowolnej wielkości, M = 5, ponieważ dysk o najmniejszym promieniu przecina co najwyżej 5 innych rozłącznych dysków (patrz rysunek).

Podobnie, gdy C jest zbiorem równoległych do osi kwadratów o dowolnym rozmiarze, M = 4.

Inne stałe można obliczyć dla innych wielokątów foremnych .

Algorytmy typu „dziel i zwyciężaj”.

Najczęstszym podejściem do znalezienia MDS jest metoda dziel i zwyciężaj. Typowy algorytm w tym podejściu wygląda następująco:

Podziel dany zestaw kształtów na dwa lub więcej podzbiorów, tak aby kształty w każdym podzbiorze nie mogły nakładać się na kształty w innych podzbiorach ze względów geometrycznych.
Rekurencyjnie znajdź MDS w każdym podzbiorze osobno.
Zwróć sumę MDS ze wszystkich podzbiorów.

Głównym wyzwaniem związanym z tym podejściem jest znalezienie geometrycznego sposobu podziału zbioru na podzbiory. Może to wymagać odrzucenia niewielkiej liczby kształtów, które nie pasują do żadnego z podzbiorów, jak wyjaśniono w kolejnych podsekcjach.

Równoległe do osi prostokąty o tej samej wysokości: 2-przybliżenie

Niech C będzie zbiorem n równoległych do osi prostokątów na płaszczyźnie, wszystkie o tej samej wysokości H , ale o różnych długościach. Poniższy algorytm znajduje zbiór rozłączny o rozmiarze co najmniej |MDS( C )|/2 w czasie O ( n log n ):

Narysuj m poziomych linii, tak aby:
1. Odstęp między dwiema liniami jest ściśle większy niż H .
2. Każda prosta przecina co najmniej jeden prostokąt (stąd m ≤ n ).
3. Każdy prostokąt przecina dokładnie jedna prosta.
Ponieważ wysokość wszystkich prostokątów wynosi H , nie jest możliwe, aby prostokąt był przecinany przez więcej niż jedną linię. $) - każdy$ linie dzielą zbiór prostokątów na m podzbiorów ( zawiera
Dla każdego podzbioru $użyciu$ dokładny MDS $jednowymiarowego$ algorytmu zachłanności (patrz wyżej
$i- 1}}$ $R_{{i-1}}$ prostokąty w ( $mogą$ $R_{i}$ prostokąty w lub w $- 1$ $R_{{i+1}}$ . Dlatego każdy z następujących dwóch związków jest zbiorem rozłącznym:
- Związek nieparzystych MDS: ${\ Displaystyle M_ {1} \ kubek M_ {3} \ kubek \ cdots}$
- Unia parzystych MDS: ${\ Displaystyle M_ {2} \ kubek M_ {4} \ kubek \ cdots}$
Zwróć największy z tych dwóch związków. Jego rozmiar musi wynosić co najmniej |MDS|/2.

Równoległe do osi prostokąty o tej samej wysokości: PTAS

Niech C będzie zbiorem n równoległych do osi prostokątów na płaszczyźnie, wszystkie o tej samej wysokości, ale o różnej długości. Istnieje algorytm, który znajduje zbiór rozłączny o rozmiarze co najmniej |MDS( C )|/(1 + 1/ k ) w czasie O ( n ^{2 k −1} ), dla każdej stałej k > 1.

Algorytm jest ulepszeniem wspomnianego powyżej 2-aproksymacji, poprzez połączenie programowania dynamicznego z techniką przesuwania Hochbauma i Maassa.

Algorytm ten można uogólnić na d wymiarów. Jeżeli etykiety mają ten sam rozmiar we wszystkich wymiarach oprócz jednego, możliwe jest znalezienie podobnego przybliżenia poprzez zastosowanie programowania dynamicznego wzdłuż jednego z wymiarów. To również skraca czas do n^O(1/e).

Prostokąty równoległe do osi: przybliżenie czynnika logarytmicznego

Niech C będzie zbiorem n równoległych do osi prostokątów na płaszczyźnie. Poniższy algorytm znajduje zbiór rozłączny o rozmiarze co najmniej ${\ Displaystyle {\ Frac {| MDS (C) |} {\ log {n}}}}$ w czasie ${\ Displaystyle O (n \ log {n})}$ :

INICJALIZACJA: posortuj poziome krawędzie podanych prostokątów według ich współrzędnej y , a krawędzie pionowe według ich współrzędnej x (ten krok zajmuje czas O ( n log n )).
WARUNEK ZATRZYMANIA: Jeśli jest co najwyżej n ≤ 2 kształtów, oblicz MDS bezpośrednio i wróć.
CZĘŚĆ REKURSYWNA:
1. Niech $\ Displaystyle x _ {\ operatorname {med}}}$ będzie środkową współrzędną x .
2. Podziel prostokąty wejściowe na trzy grupy zgodnie z ich relacją do linii ${\ operatorname {lewo}}}$ $mi$ stronie ( ${\$ ), te całkowicie po jego prawej stronie ( ${\ Displaystyle R _ {\ operatorname {po prawej}}})$ i te przecinane przez niego ( ${\ Displaystyle R_ {\mathrm {int}}}$ ). Z konstrukcji liczności ${\ Displaystyle R _ {\ operatorname {lewo}}}$ i ${\ Displaystyle R _ {\ operatorname {po prawej}}}$ są co najwyżej n /2.
3. Rekurencyjnie oblicz przybliżony MDS w ${\ Displaystyle R _ {\ operatorname {lewo}}}$ ( ${\ Displaystyle M _ {\ operatorname {lewo}}})$ i ${\ Displaystyle R _ {\ operatorname {po prawej}}}$ ( ${\ Displaystyle M _ {\ operatorname {po prawej}}}$ ) i obliczyć ich związek. Z założenia prostokąty w ${\ Displaystyle M _ {\ operatorname {lewo}}}$ i ${\ Displaystyle M _ {\ operatorname {po prawej}}}$ są rozłączne, więc ${\ Displaystyle M _ {\ operatorname {po lewej}} \ puchar M_ {\ operatorname {po prawej}}}$ jest zbiorem rozłącznym.
4. Oblicz dokładny MDS w ${\ displaystyle R _ {\ operatorname {int}}}$ ( ${\ displaystyle M _ {\ operatorname {int}}})$ . Ponieważ wszystkie prostokąty w ${\ Displaystyle R _ {\ operatorname {int}}}$ przecinają pojedynczą linię pionową ${\ Displaystyle x = x _ {\ operatorname {med}}}$ , to obliczenie jest równoważne znalezieniu MDS ze zbioru przedziałów i można je rozwiązać dokładnie w czasie O (n log n) (patrz wyżej).
Zwróć albo ${\ Displaystyle M _ {\ operatorname {lewo}} \ kubek M _ {\ operatorname {po prawej}}}$ lub ${\ Displaystyle M _ {\ operatorname {int } }}$ – w zależności od tego, która z nich jest większa.

Można udowodnić przez indukcję, że na ostatnim etapie albo ${\ Displaystyle M _ {\ operatorname {po lewej}} \ kubek M _ {\ operatorname {po prawej}}}$ lub ${\ Displaystyle M _ {\ operatorname {int}}}$ mają liczność co najmniej ${\ Displaystyle {\ Frac {| MDS (C) |} {\ log {n}}}}$ .

Chalermsookk i Chuzoy poprawili współczynnik do ${\ Displaystyle O (\ log {\ log {n}})}$ .

Chalermsook i $Walczak$ przedstawili do bardziej ogólnego ustawienia, w którym wagę polega na znalezieniu niezależnego zestawu maksymalnej masy całkowitej.

Prostokąty równoległe do osi: przybliżenie ze stałym współczynnikiem

Przez długi czas nie było wiadomo, czy istnieje przybliżenie ze stałym współczynnikiem dla równoległych do osi prostokątów o różnych długościach i wysokościach. Przypuszczano, że takie przybliżenie można znaleźć za pomocą cięć gilotynowych . W szczególności, jeśli istnieje separacja gilotynowa prostokątów równoległych do osi, w której $to$ można jej użyć w podejściu do programowania dynamicznego, aby znaleźć przybliżenie o stałym MDS.

Do dziś nie wiadomo, czy taka gilotynowa separacja istnieje. Istnieją jednak algorytmy aproksymacji ze stałym współczynnikiem wykorzystujące cięcia inne niż gilotynowe:

Joseph SB Mitchell przedstawił 10-czynnikowy algorytm aproksymacji. Jego algorytm opiera się na podziale płaszczyzny na prostokąty o ściętych rogach .
Gálvez, Khan, Mari, Mömke, Pittu i Wiese przedstawili algorytm dzielący płaszczyznę na bardziej ogólną klasę wielokątów. Upraszcza to analizę i poprawia przybliżenie do współczynnika 6. Dodatkowo poprawili przybliżenie do współczynnika 3, a następnie do współczynnika (2+ε).

Grube przedmioty o identycznych rozmiarach: PTAS

Niech C będzie zbiorem n kwadratów lub kół tej samej wielkości. Hochbaum i Maass przedstawili schemat aproksymacji w czasie wielomianowym do znajdowania MDS przy użyciu prostej strategii z przesuniętą siatką. Znajduje rozwiązanie w obrębie (1 − ε) maksimum w czasie n ^{O (1/ ε ² )} czasu i przestrzeni liniowej. Strategia uogólnia się na dowolną kolekcję grubych obiektów o mniej więcej tej samej wielkości (tj. gdy stosunek wielkości maksymalnej do minimalnej jest ograniczony stałą).

Grube obiekty o dowolnych rozmiarach: PTAS

Niech C będzie zbiorem n grubych przedmiotów , takich jak kwadraty lub koła , o dowolnych rozmiarach. Istnieje PTAS do znajdowania MDS w oparciu o wielopoziomowe wyrównanie siatki. Został odkryty przez dwie grupy mniej więcej w tym samym czasie i opisany na dwa różne sposoby.

Partycjonowanie na poziomie

Algorytm Erlebacha, Jansena i Seidela znajduje zbiór rozłączny o rozmiarze co najmniej (1 − 1/ k ) ² · |MDS( C )| w czasie n ^{O ( k ² )} , dla każdej stałej k > 1. Działa to w następujący sposób.

Skaluj dyski tak, aby najmniejszy miał średnicę 1. Podziel dyski na poziomy w oparciu o logarytm ich rozmiaru. To znaczy, j -ty poziom zawiera wszystkie krążki o średnicy pomiędzy ( k + 1) ^j a ( k + 1) ^{j +1} , dla j ≤ 0 (najmniejszy krążek znajduje się na poziomie 0).

Dla każdego poziomu j nałóż na płaszczyznę siatkę składającą się z linii oddalonych od siebie o ( k + 1) ^{j +1 .} Z założenia każdy dysk może przecinać co najwyżej jedną linię poziomą i jedną linię pionową od swojego poziomu.

Dla każdego r , s między 0 a k zdefiniuj D ( r , s ) jako podzbiór dysków, które nie są przecięte przez żadną linię poziomą, której indeks modulo k wynosi r , ani przez żadną linię pionową, której indeks moduluk k wynosi s . Zgodnie z zasadą przegródki istnieje co najmniej jedna para (r,s) taka, że ${\ Displaystyle | \ operatorname {MDS} (D (r, s)} | \ geq (1- {\ Frac {1} {k}}) ^ {2} \ cdot | \ operatorname {MDS} |}, tj$ . , możemy znaleźć MDS tylko w D ( r , s ) i pominąć tylko niewielką część dysków w rozwiązaniu optymalnym:

Dla wszystkich k ² możliwych wartości r , s (0 ≤ r , s < k ) oblicz D ( r , s ) używając programowania dynamicznego .
Zwróć największy z tych k ² zestawów.

Przesunięte czworokąty

Drzewo czwórkowe regionu z danymi punktowymi

Algorytm Chan znajduje zbiór rozłączny o rozmiarze co najmniej (1 − 2/ k )·|MDS( C )| w czasie n ^{O ( k )} , dla każdej stałej k > 1.

Algorytm wykorzystuje przesunięte drzewa czworokątne . Kluczową koncepcją algorytmu jest wyrównanie do siatki quadtree. Obiekt o rozmiarze r nazywany jest wyrównanym do k (gdzie k ≥ 1 jest stałą), jeśli znajduje się w komórce drzewa czworokątnego o rozmiarze co najwyżej kr ( R ≤ kr ).

Z definicji obiekt wyrównany do k , który przecina granicę poczwórnej komórki o rozmiarze R , musi mieć rozmiar co najmniej R / k ( r > R / k ). Granicę komórki o rozmiarze R można pokryć 4 k kwadratów o rozmiarze R / k ; stąd liczba rozłącznych obiektów tłuszczowych przecinających granicę tej komórki wynosi co najwyżej 4 kc , gdzie c jest stałą mierzącą otłuszczenie obiektów.

Dlatego, jeśli wszystkie obiekty są wyrównane do grubych i k , możliwe jest znalezienie dokładnego maksymalnego zbioru rozłącznego w czasie n ^{O ( kc )} za pomocą algorytmu dziel i zwyciężaj. Zacznij od komórki drzewa czworokątnego, która zawiera wszystkie obiekty. Następnie rekurencyjnie podziel go na mniejsze komórki czworokątne, znajdź maksimum w każdej mniejszej komórce i połącz wyniki, aby uzyskać maksimum w większej komórce. Ponieważ liczba rozłącznych obiektów tłuszczowych przecinających granicę każdej komórki drzewa czworokątnego jest ograniczona przez 4 kc , możemy po prostu „zgadnąć”, które obiekty przecinają granicę w optymalnym rozwiązaniu, a następnie zastosować metodę dziel i zwyciężaj do obiektów w środku.

Jeśli prawie wszystkie obiekty są wyrównane do k , możemy po prostu odrzucić obiekty, które nie są wyrównane do k , i znaleźć maksymalny rozłączny zbiór pozostałych obiektów w czasie n ^{O ( k )} . Daje to przybliżenie (1 - e ), gdzie e jest ułamkiem obiektów, które nie są wyrównane do k .

Jeśli większość obiektów nie jest wyrównana do k , możemy spróbować ustawić je wyrównane do k , przesuwając siatkę o wielokrotności (1/ k , 1/ k ). Najpierw przeskaluj obiekty tak, aby wszystkie mieściły się w kwadracie jednostkowym. Następnie rozważ k przesunięć siatki: (0,0), (1/ k ,1/ k ), (2/ k ,2/ k ), ..., (( k − 1)/ k , ( k − 1)/ k ). Tj. dla każdego j w {0,..., k − 1}, rozważ przesunięcie siatki w (j/k, j/k). Można udowodnić, że każda etykieta będzie wyrównana do 2 k dla co najmniej k − 2 wartości j . Teraz dla każdego j odrzuć obiekty, które nie są wyrównane do k w przesunięciu ( j / k , j / k ) i znajdź maksymalny rozłączny zbiór pozostałych obiektów. Nazwijmy ten zestaw A ( j ). Zadzwoń do rzeczywistego maksymalnego zestawu rozłącznego A *. Następnie:

${\ Displaystyle \ suma _ {j = 0, \ ldots, k-1} {| A (j) |} \ geq (k-2) | A * |}$

Zatem największe A ( j ) ma rozmiar co najmniej: (1 − 2/ k )| * |. Wartość zwracana przez algorytm to największa A ( j ); współczynnik aproksymacji wynosi (1 - 2/ k ), a czas działania to n ^{O ( k )} . Możemy sprawić, że współczynnik aproksymacji będzie tak mały, jak chcemy, więc to jest PTAS .

Obie wersje można uogólnić na wymiary d (z różnymi współczynnikami przybliżenia) i na przypadek ważony.

Algorytmy separatora geometrycznego

Kilka algorytmów typu „dziel i zwyciężaj” opiera się na pewnym twierdzeniu o separatorze geometrycznym . Separator geometryczny to linia lub kształt, który oddziela dany zestaw kształtów na dwa mniejsze podzbiory, tak że liczba kształtów traconych podczas podziału jest stosunkowo niewielka. Pozwala to zarówno na algorytmy PTAS , jak i subwykładnicze algorytmy dokładne, jak wyjaśniono poniżej.

Grube obiekty o dowolnych rozmiarach: PTAS z użyciem separatorów geometrycznych

Niech C będzie zbiorem n grubych przedmiotów , takich jak kwadraty lub koła, o dowolnych rozmiarach. Chan opisał algorytm, który znajduje zbiór rozłączny o rozmiarze co najmniej (1 − O ( √ b ))·|MDS( C )| w czasie n ^{O ( b )} , dla każdej stałej b > 1.

Algorytm opiera się na następującym twierdzeniu o separatorze geometrycznym, które można udowodnić podobnie jak dowód istnienia separatora geometrycznego dla kwadratów rozłącznych :

Dla każdego zestawu C grubych obiektów istnieje prostokąt, który dzieli C na trzy podzbiory obiektów – C _wewnątrz , C _{na zewnątrz} i C _brzeg , takie że:

|MDS( C _wewnątrz )| ≤ za |MDS( do )|
|MDS( C _{na zewnątrz} )| ≤ a|MDS( do )|
|MDS( C _granica )| do √ | MDS( C ) |

gdzie a i c są stałymi. Gdybyśmy mogli dokładnie obliczyć MDS( C ), moglibyśmy obniżyć stałą a do 2/3 przez odpowiedni wybór prostokąta separatora. Ale ponieważ MDS( C ) możemy przybliżyć tylko stałym współczynnikiem, stała a musi być większa. Na szczęście a pozostaje stałą niezależną od | C |.

To twierdzenie o separatorze pozwala zbudować następujący PTAS:

Wybierz stałą b . Sprawdź wszystkie możliwe kombinacje aż do b + 1 etykiet.

Jeżeli |MDS( C )| ma rozmiar co najwyżej b (tj. wszystkie zestawy etykiet b + 1 nie są rozłączne), to po prostu zwróć ten MDS i wyjdź. Ten krok zajmuje n ^{O ( b )} czasu.
W przeciwnym razie użyj separatora geometrycznego, aby rozdzielić C na dwa podzbiory. Znajdź przybliżony MDS w C _wewnątrz i C _{na zewnątrz} osobno i zwróć ich kombinację jako przybliżony MDS w C .

Niech E ( m ) będzie błędem powyższego algorytmu, gdy optymalnym rozmiarem MDS jest MDS ( C ) = m . Gdy m ≤ b , błąd wynosi 0, ponieważ maksymalny zbiór rozłączny jest obliczany dokładnie; gdy m > b , błąd zwiększa się co najwyżej o c √ m liczbę etykiet przeciętych separatorem. Najgorszy przypadek algorytmu ma miejsce, gdy podział w każdym kroku jest w maksymalnym możliwym stosunku, który wynosi a :(1 − a ). Dlatego funkcja błędu spełnia następującą relację powtarzalności:

{\ Displaystyle E (m) = 0 \ \ \ {\ tekst {jeśli}} m \ równoważnik b}

{\ Displaystyle E (m) = E (a \ cdot m) + E ((1-a) \ cdot m) + c \ cdot {\ sqrt {m }}{\text{jeśli }}m>b}

Rozwiązaniem tego powtórzenia jest:

{\ Displaystyle E (m) = ({\ Frac {0} {b}} + {\ Frac {c} {{\ sqrt {b}} ({\ sqrt {a}} + {\ sqrt {1-a }}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}. }

tj. ${\ Displaystyle E (m) = O (m / {\ sqrt {b}})}$ . Możemy sprawić, że współczynnik aproksymacji będzie tak mały, jak chcemy, przez odpowiedni wybór b .

Ten PTAS jest bardziej wydajny przestrzennie niż PTAS oparty na drzewach czworokątnych i może obsłużyć uogólnienie, w którym obiekty mogą się przesuwać, ale nie radzi sobie z przypadkiem ważonym.

Dyski o ograniczonym stosunku wielkości do rozmiaru: dokładny algorytm podwykładniczy

Niech C będzie zbiorem n krążków, tak że stosunek największego i najmniejszego promienia wynosi co najwyżej r . Poniższy algorytm wyszukuje MDS ( do ) dokładnie w czasie ${\ Displaystyle 2 ^ {O (r \ cdot {\ sqrt {n}})}}$ .

Algorytm oparty jest na geometrycznym separatorze o ograniczonej szerokości na zbiorze Q środków wszystkich dysków w C . To twierdzenie o separatorze pozwala zbudować następujący dokładny algorytm:

Znajdź linię rozdzielającą taką, że co najwyżej 2 n /3 środków jest po jej prawej stronie ( C _right ), co najwyżej 2 n /3 centrów jest po jej lewej stronie ( C _left ) i co najwyżej O ( √ n ) centrów leży po odległość mniejsza niż r /2 od linii ( _Cint ) .
Rozważ wszystkie możliwe nienakładające się podzbiory C _int . Istnieją $_$ _ Dla każdego takiego podzbioru oblicz rekurencyjnie MDS C _left i MDS C _right i zwróć największy połączony zbiór.

Czas działania tego algorytmu spełnia następującą zależność powtarzalności:

{\ Displaystyle T (1) = 1}

{\ Displaystyle T (n) = 2 ^ {O (r\cdot {\sqrt {n}})}T\left({\frac {2n}{3}}\right){\text{if }}n>1}

Rozwiązaniem tego powtórzenia jest:

{\ Displaystyle T (n) = 2 ^ {O (r \ cdot {\ sqrt {n}})}}

Lokalne algorytmy wyszukiwania

Pseudodyski: PTAS

Pseudo -zbiór dysków jest zbiorem obiektów w którym granice każdej pary obiektów przecinają się co najwyżej dwa razy (Zauważże ta definicja odnosi się do całej kolekcji i nie mówi nic o kształtach poszczególnych obiektów w kolekcji ). Pseudo-zbiór dysków ma ograniczoną złożoność unii, tj. liczba punktów przecięcia na granicy unii wszystkich obiektów jest liniowa względem liczby obiektów. Na przykład zestaw kwadratów lub kół o dowolnych rozmiarach to pseudo-zbiór dysków.

Niech C będzie pseudo-zbiorem dysków z n obiektami. Lokalny algorytm wyszukiwania autorstwa Chana i Har-Peleda znajduje rozłączny zbiór o rozmiarze co najmniej ${\ Displaystyle (1-O ({\ Frac {1} {\ sqrt {b}}})} \ cdot |MDS (C) |}$ w czasie ${\ Displaystyle O (n ^ { b+3})}$ , dla każdej stałej całkowitej ${\ Displaystyle b \ geq 0}$ :

INICJALIZACJA: Zainicjuj pusty zestaw, ${\ displaystyle S}$ .
WYSZUKIWANIE: Zapętl wszystkie podzbiory $displaystyle$ $C-S$ 1 do $b + 1}$ $b+1$ . Dla każdego takiego podzbioru X :
- Sprawdź, czy sam X jest niezależny (w przeciwnym razie przejdź do następnego podzbioru);
- Oblicz zbiór Y obiektów w S , które przecinają X .
- Jeśli ${\ Displaystyle | Y|<| X|}$ , następnie usuń Y z S i wstaw X : ${\ Displaystyle S: = SY + X}$ .
KONIEC: zwróć zestaw S .

Każda wymiana w kroku wyszukiwania zwiększa rozmiar S o co najmniej 1, a zatem może się zdarzyć co najwyżej n razy.

Algorytm jest bardzo prosty; najtrudniejszą częścią jest udowodnienie współczynnika przybliżenia.

Zobacz też.

Algorytmy relaksacyjne programowania liniowego

Pseudodyski: PTAS

Niech C będzie pseudo-zbiorem dysków z n obiektami i złożonością unii u . Korzystając z relaksacji programowania liniowego , można znaleźć zbiór rozłączny o rozmiarze co najmniej ${\ Displaystyle {\ Frac {n} {u}} \ cdot |MDS (C) |}$ . Jest to możliwe za pomocą losowego algorytmu, który ma duże prawdopodobieństwo sukcesu i czas działania ${\ Displaystyle O (n ^ {3})}$ , lub algorytm deterministyczny z wolniejszym czasem działania (ale nadal wielomian). Algorytm ten można uogólnić na przypadek ważony.

Inne klasy kształtów, dla których znane są przybliżenia

Segmenty linii w płaszczyźnie dwuwymiarowej.
Dowolne dwuwymiarowe obiekty wypukłe .
Krzywe z ograniczoną liczbą punktów przecięcia.

Linki zewnętrzne

Notatki