Separator geometryczny

Separator geometryczny to linia (lub inny kształt), która dzieli zbiór kształtów geometrycznych na dwa podzbiory, w taki sposób, że proporcja kształtów w każdym podzbiorze jest ograniczona, a liczba kształtów, które nie należą do żadnego podzbioru (tj. przez sam separator) jest niewielka.

Gdy istnieje separator geometryczny, można go wykorzystać do budowania algorytmów typu „dziel i zwyciężaj” do rozwiązywania różnych problemów w geometrii obliczeniowej .

Separatory będące liniami

Pytanie ogólne

W 1979 roku Helge Tverberg zadał następujące pytanie. Dla dwóch dodatnich liczb całkowitych k , l , jaka jest najmniejsza liczba n ( k , l ) taka, że dla dowolnej rodziny rozłącznych parami wypukłych obiektów na płaszczyźnie istnieje prosta, która ma co najmniej k obiektów po jednej stronie i przynajmniej ja po drugiej stronie?

Znane są następujące wyniki.

Oczywiście n (1,1)=1.
Hope i Katchalski udowodnili, że n ( k ,1) ≤ 12( k -1) dla wszystkich k ≥ 2.
Villager udowodnił, że n(2,2) = ∞: pokazał nieskończoną rodzinę segmentów rozłącznych parami, tak że żadna prosta nie ma dwóch odcinków z każdej strony. Pach i Tardos pokazali prostszą konstrukcję wykorzystującą tylko segmenty jednostek i inną konstrukcję wykorzystującą tylko dyski (lub kwadraty).

Separatory dla prostokątów równoległych do osi

Mając zbiór N = 4 k rozłącznych równoległych do osi prostokątów na płaszczyźnie, istnieje taka linia, pozioma lub pionowa, w której co najmniej N / 4 prostokątów leży całkowicie po obu jej stronach (a więc co najwyżej N / 2 prostokątów przecinają się linią rozdzielającą).

Dowód

Zdefiniuj W jako najbardziej wysuniętą na zachód linię pionową z co najmniej N /4 prostokątami całkowicie na zachód. Istnieją dwa przypadki:

na wschód od W znajduje się co najmniej N /4 prostokątów , wówczas W jest separatorem pionowym.
W przeciwnym razie, przesuwając W nieco na zachód, otrzymamy linię pionową, która przecina więcej niż N /2 prostokątów. Znajdź punkt na tej linii, który ma co najmniej N /4 prostokątów powyżej i N /4 prostokątów poniżej, i narysuj przez niego poziomy separator.

optymalność

Liczba przecinających się kształtów, gwarantowana powyższym twierdzeniem, wynosi O( N ). Ta górna granica jest asymptotycznie ciasna, nawet gdy kształty są kwadratami, jak pokazano na rysunku po prawej stronie. Stoi to w ostrym kontraście z górną granicą przecinających się kształtów O ( √ N ), która jest gwarantowana, gdy separatorem jest kształt zamknięty (patrz poprzednia sekcja ).

Ponadto, gdy kształty są dowolnymi prostokątami, istnieją przypadki, w których żadna linia oddzielająca więcej niż jeden prostokąt nie może przecinać mniej niż N /4 prostokątów, jak pokazano na rysunku po prawej stronie.

Uogólnienia

Powyższe twierdzenie można uogólnić z rozłącznych prostokątów na k -grube prostokąty. Dodatkowo, przez indukcję po d , można uogólnić powyższe twierdzenie na wymiary d i otrzymać następujące twierdzenie:

Biorąc pod uwagę N równoległych do osi d -pudeł, których wnętrza są k -grube, istnieje równoległa do osi hiperpłaszczyzna taka, że co najmniej:

{\ Displaystyle \ lfloor (N + 1 -k)/(2d)\rfloor }

wnętrz d -boksów leży po obu stronach hiperpłaszczyzny.

W szczególnym przypadku, gdy k = N - 1 (tj. każdy punkt jest zawarty w co najwyżej N - 1 kratkach), obowiązuje następujące twierdzenie:

Biorąc pod uwagę N równoległych do osi d -pudeł, których wnętrza mają grubość ( N - 1), istnieje hiperpłaszczyzna równoległa do osi, która oddziela dwa z nich.

Obiekty nie muszą być pudełkami, a separatory nie muszą być równoległe do osi:

Niech C będzie zbiorem możliwych orientacji hiperpłaszczyzn (tzn. C = {horizontal,vertical}). Dla danych N d -obiektów, takich, że każde dwa rozłączne obiekty są oddzielone hiperpłaszczyzną o orientacji z C , której wnętrza są k -grube, istnieje hiperpłaszczyzna o orientacji z C taka, że co najmniej: ( N + 1 − k )/O( C ) wnętrz d -obiektów leży całkowicie po obu stronach hiperpłaszczyzny.

Wersje algorytmiczne

Możliwe jest znalezienie hiperpłaszczyzn gwarantowanych powyższymi twierdzeniami w krokach O( Nd ). Ponadto, jeśli listy 2 d dolnych i górnych punktów końcowych przedziałów definiujących i -te współrzędne pudełek są wstępnie posortowane, to najlepsza taka hiperpłaszczyzna (według szerokiej gamy miar optymalności) może znajdować się w O( Nd ) kroki.

Separatory, które są zamkniętymi kształtami

Prosty przypadek, w którym zagwarantowane jest istnienie separatora, jest następujący:

Biorąc pod uwagę zbiór n rozłącznych równoległych do osi kwadratów na płaszczyźnie, istnieje prostokąt R taki, że co najwyżej 2 n /3 kwadratów znajduje się wewnątrz R , co najwyżej 2 n /3 kwadratów znajduje się na zewnątrz R i co najwyżej większość O(sqrt( n )) kwadratów nie znajduje się wewnątrz ani na zewnątrz R (tj. przecina granicę R ).

Zatem R jest separatorem geometrycznym, który dzieli n kwadratów na dwa podzbiory („wewnątrz R ” i „na zewnątrz R ”) ze stosunkowo niewielką „stratą” (kwadraty przecięte przez R są uważane za „utracone”, ponieważ nie należą do do dowolnego z dwóch podzbiorów).

Dowód

Zdefiniuj prostokąt 2-gruby jako równoległy do osi prostokąt o współczynniku proporcji co najwyżej 2.

₀₀ Niech R będzie 2-grubym prostokątem o minimalnym polu, zawierającym środki co najmniej n /3 kwadratów. Zatem każdy 2-tłuszczowy prostokąt mniejszy niż R zawiera mniej niż n /3 kwadratów.

₀ Dla każdego t w [0,1), niech R _t będzie 2-grubym prostokątem o tym samym środku co R , powiększonym o 1 + t .

₀ R _t zawiera R , więc zawiera środki co najmniej n /3 kwadratów.
₀₀ R _t jest mniej niż dwa razy większe niż R , więc można je przykryć dwoma prostokątami 2-tłuszczowymi, które są mniejsze niż R . Każdy z tych 2-grubych prostokątów zawiera środki mniejsze niż n /3 kwadratów. Zatem R _t zawiera centra mniejsze niż 2 n /3 kwadratów.

Teraz pozostaje pokazać, że istnieje t , dla którego R _t przecina się co najwyżej O(sqrt( n )) kwadratów.

₀₀ Najpierw rozważ wszystkie „duże kwadraty” - kwadraty, których długość boku wynosi co najmniej ${\ Displaystyle \ operatorname {szerokość} (R_ {0}) / 2 {\ sqrt {n}} }$ . Dla każdego t obwód R _t wynosi co najwyżej 2 · obwód ( R ), co najwyżej 6 · szerokość ( R ), więc może przecinać co najwyżej $sqrt {n}}}$ \ kwadraty.

Następnie rozważ wszystkie „małe kwadraty” - kwadraty, których długość boku jest mniejsza niż ${\ Displaystyle \ operatorname {szerokość} (R_ {0}) / 2 {\ sqrt {n}} }$ .

Dla każdego t zdefiniujmy: przecięcie( t ) jako zbiór małych kwadratów przeciętych granicą R _t . Dla każdego t ₁ i t ₂ , jeśli ${\ Displaystyle | t_ {1} -t_ {2} | \ geq 1 / {\ sqrt {n}}}$ , a następnie ${\ Displaystyle | \ nazwa operatora {szerokość} (R_ {t_ {1}}) - \ nazwa operatora {szerokość} (R_ {t_ {2}}) | \ geq \ nazwa operatora {szerokość} ( R_{0})/{\sqrt {n}}}$ . Dlatego między granicą R _{t ₁} a granicą jest przerwa o ${\ Displaystyle \ operatorname {szerokość} (R_ {0})/2 {\ sqrt {n}}}$ z Rt _{_ ₂} . Zatem przecięcie( t ₁ ) i przecięcie ( t ₂ ) są rozłączne. Dlatego:

{\ Displaystyle \ suma _ {j = 0} ^ {{\ sqrt {n}} -1} {| \ operatorname {przecięcie} (j / {\ sqrt {n}}) |} \ równoważnik n}

₀ Zatem zgodnie z zasadą przegródki istnieje pewne j, dla którego:

{\ Displaystyle | \ nazwa operatora {przecięcie} (j_ {0} / {\ sqrt {n}}) | \ równoważnik {\ sqrt {n}}}

Separatorem, którego szukamy, jest prostokąt R _t , gdzie ${\ displaystyle t = j_ {0}/ {\ sqrt {n}}}$ .

Przykład zastosowania

Korzystając z tego twierdzenia o separatorze, możemy rozwiązać pewne problemy w geometrii obliczeniowej w następujący sposób:

Rozdziel wejściowy zbiór kwadratów na dwa rozłączne podzbiory;
Rozwiąż problem dla każdego podzbioru osobno;
Połącz rozwiązania dwóch podproblemów i uzyskaj przybliżone rozwiązanie pierwotnego problemu.

Uogólnienia

Powyższe twierdzenie można uogólnić na wiele różnych sposobów, z możliwie różnymi stałymi. Na przykład:

Zamiast kwadratów kolekcja wejściowa może zawierać dowolne grube obiekty , takie jak: koła, prostokąty o ograniczonych proporcjach itp.
Zamiast dwuwymiarowych kształtów na płaszczyźnie, zbiór danych wejściowych może zawierać obiekty o dowolnym wymiarze, które mogą być umieszczone w d -wymiarowym torusie .
Zamiast wymagać, aby kształty w zbiorze wejściowym były rozłączne, możemy postawić słabszy wymóg, aby zbiór był:
- k-grubości , tj. każdy punkt jest pokryty co najwyżej k różnymi kształtami.
- lk-grubości , tj. każdy punkt jest pokryty co najwyżej k różnymi kształtami o stosunku wielkości (rozmiar największego kształtu podzielony przez rozmiar najmniejszego kształtu) co najwyżej l .
- k-przeciążony , tj. dla dowolnego podzbioru kształtów suma ich indywidualnych miar jest co najwyżej k razy większa od miary ich sumy.
Zamiast prostokątnego separatora separator może mieć dowolny kształt, który można pokryć jego mniejszymi kopiami.
Zamiast ograniczać liczbę kształtów po każdej stronie separatora, można ograniczyć dowolną miarę, która spełnia określone aksjomaty.

optymalność

Stosunek 1:2 w powyższym twierdzeniu o separatorze kwadratowym jest najlepszym, jaki można zagwarantować: istnieją zbiory kształtów, których nie można rozdzielić w lepszym stosunku przy użyciu separatora, który przecina tylko kształty O(sqrt(n) ) . Oto jeden taki zbiór (z twierdzenia 34 z ):

Rozważmy trójkąt równoboczny . Na każdym z jej 3 wierzchołków umieść N /3 figur ułożonych w spiralę wykładniczą, tak aby średnica zwiększała się o stały czynnik przy każdym obrocie spirali, a każda figura stykała się z sąsiednimi w porządku spirali. Na przykład zacznij od prostokąta o wymiarach 1 na Φ, gdzie Φ to złoty podział . Dodaj sąsiedni kwadrat Φ na Φ i uzyskaj kolejny złoty prostokąt. Dodaj sąsiedni kwadrat (1+Φ) na (1+Φ) i uzyskaj większy złoty prostokąt i tak dalej.

Teraz, aby oddzielić więcej niż 1/3 kształtów, separator musi oddzielić kształty O( N ) z dwóch różnych wierzchołków. Ale aby to zrobić, separator musi przecinać kształty O ( N ).

Separatory, które są paskami o ograniczonej szerokości między równoległymi hiperpłaszczyznami

Niech Q będzie zbiorem n punktów na płaszczyźnie takich, że minimalna odległość między punktami wynosi d . Niech a >0 będzie stałą.

Istnieje para równoległych linii odległości a , takich że co najwyżej 2 n / 3 punkty leżą po każdej stronie paska i co najwyżej

{n }}}

punktów leży wewnątrz paska.

Równoważnie: istnieje taka linia, że co najwyżej 2

/

punkty leżą po jej stronie i co najwyżej leżą na a odległości mniejszej niż a /2 od niego.

Szkic dowodowy

Zdefiniuj środek Q jako punkt o taki, że każda prosta przechodząca przez niego ma co najwyżej 2 n /3 punktów Q po każdej stronie . Istnienie punktu środkowego można udowodnić za pomocą twierdzenia Helly'ego .

Dla danego punktu p i stałej a >0 zdefiniuj Pr(a,p,o) jako prawdopodobieństwo, że losowa prosta przechodząca przez o leży w odległości mniejszej niż a od p . Chodzi o to, aby ograniczyć to prawdopodobieństwo, a tym samym ograniczyć oczekiwaną liczbę punktów w odległości mniejszej niż a od losowej linii przechodzącej przez o . Wtedy, zgodnie z zasadą przegródki , co najmniej jedna linia przechodząca przez o jest pożądanym separatorem.

Aplikacje

Separatory o ograniczonej szerokości mogą być użyte do przybliżonego rozwiązania problemu fałdowania białek . Można go również użyć w dokładnym algorytmie subwykładniczym do znalezienia maksymalnego niezależnego zestawu , a także kilku powiązanych problemów pokrycia w grafach geometrycznych.

Separatory geometryczne i separatory grafów planarnych

Twierdzenie o separatorze planarnym można udowodnić, używając twierdzenia o upakowaniu okręgu do przedstawienia wykresu planarnego jako wykresu kontaktowego układu dysków na płaszczyźnie, a następnie znajdując okrąg, który tworzy separator geometryczny dla tych dysków.

Zobacz też

Twierdzenie Ham Sandwich : mając n mierzalnych obiektów w n -wymiarowej przestrzeni, można je wszystkie podzielić na pół (ze względu na ich miarę, tj. objętość) za pomocą jednowymiarowej ( n − 1)-wymiarowej hiperpłaszczyzny.
Separacja gilotynowa : problem separacji przedmiotów wypukłych w płaszczyźnie za pomocą cięć gilotynowych.
Inne twierdzenia o separacji .
Separator równoczesny: separator, który jednocześnie oddziela kształty w kilku kolekcjach, jednocześnie przecinając niewielką liczbę kształtów w każdej kolekcji, może nie zawsze istnieć.

Notatki