Kula ograniczająca

Niektóre przypadki najmniejszego okręgu ograniczającego , przypadek sfery ograniczającej w 2 wymiarach.

W matematyce , biorąc pod uwagę niepusty zbiór obiektów o skończonej rozciągłości w $przestrzeni$ , na przykład zbiór punktów, kulę ograniczającą , otaczającą kulę lub otaczającą piłkę dla tego zestawu, re $displaystyle d} d}$ \ -wymiarowa bryła zawierająca wszystkie te obiekty.

Stosowana w grafice komputerowej i geometrii obliczeniowej kula ograniczająca jest szczególnym rodzajem objętości ograniczającej . Istnieje kilka szybkich i prostych algorytmów konstruowania sfer ograniczających o dużej wartości praktycznej w aplikacjach grafiki komputerowej czasu rzeczywistego.

W statystyce i badaniach operacyjnych obiektami są zwykle punkty, a sferą zainteresowania jest minimalna sfera ograniczająca , to znaczy sfera o minimalnym promieniu spośród wszystkich sfer ograniczających. Można udowodnić, że taka kula jest wyjątkowa: jeśli są dwie, to przedmiotowe obiekty leżą na ich przecięciu. Ale przecięcie dwóch nienachodzących na siebie kul o jednakowym promieniu zawiera się w kuli o mniejszym promieniu.

Problem obliczania środka minimalnej sfery ograniczającej jest również znany jako „nieważony euklidesowy problem 1-centrum ”.

Aplikacje

Grupowanie

Takie sfery są przydatne w grupowaniu , gdzie grupy podobnych punktów danych są klasyfikowane razem.

W analizie statystycznej rozproszenie punktów danych w kuli można przypisać błędowi pomiaru lub procesom naturalnym (zwykle termicznym), w którym to przypadku klaster reprezentuje zaburzenie idealnego punktu. W pewnych okolicznościach ten idealny punkt może być użyty jako substytut punktów w klastrze, co jest korzystne w skróceniu czasu obliczeń.

W badaniach operacyjnych klasteryzacja wartości do punktu idealnego może być również wykorzystana do zmniejszenia liczby danych wejściowych w celu uzyskania przybliżonych wartości dla problemów NP-trudnych w rozsądnym czasie. Wybrany punkt zwykle nie jest środkiem kuli, ponieważ może to być obciążone wartościami odstającymi, ale zamiast tego obliczana jest jakaś forma średniej lokalizacji, taka jak najmniejszych kwadratów , reprezentujący klaster.

Algorytmy

Istnieją dokładne i przybliżone algorytmy rozwiązywania problemu sfery ograniczającej.

Programowanie liniowe

Nimrod Megiddo intensywnie badał problem 1-centrum i publikował go co najmniej pięć razy w latach 80. W 1983 roku zaproponował algorytm „ przycinania i wyszukiwania ”, który znajduje optymalną sferę ograniczającą i działa w czasie liniowym, jeśli wymiar jest stały. Biorąc pod uwagę wymiar, złożoność czasu wykonania jest niepraktyczna dla wysokich ${\ Displaystyle O ((d + 1) (d + 1)! n)}$ aplikacje wymiarowe. Megiddo zastosował to podejście do programowania liniowego w czasie liniowym, gdy wymiar jest ustalony.

W 1991 roku Emo Welzl zaproponował znacznie prostszy algorytm randomizowany , oparty na rozszerzeniu algorytmu randomizowanego programowania liniowego autorstwa Raimunda Seidela . Działa w oczekiwanym czasie liniowym. W artykule przedstawiono wyniki eksperymentalne demonstrujące jego praktyczność w wyższych wymiarach.

Biblioteka algorytmów geometrii obliczeniowej typu open source (CGAL) zawiera implementację tego algorytmu.

Kula ograniczająca Rittera

W 1990 roku Jack Ritter zaproponował prosty algorytm znajdowania nieminimalnej sfery ograniczającej. Jest szeroko stosowany w różnych aplikacjach ze względu na swoją prostotę. Algorytm działa w ten sposób:

Wybierz punkt $od$ $wyszukaj$ punkt $;$ $_$ $który$ ma odległość _
Wyszukaj punkt $\$ , który ma największą odległość od $y$ $}$ . Ustaw początkową piłkę ${$ $środkiem$ jako środkiem i $\ displaystyle z}$ ${$ , promieniem jako połową odległości między $\ displaystyle y}$ i $\displaystyle z}$ ;
Jeśli wszystkie punkty w $znajdują$ się w kuli to otrzymujemy sferę $ograniczającą$ W przeciwnym razie niech będzie $punktem$ poza piłką, skonstruuj nową piłkę obejmującą zarówno punkt, $i$ piłkę. Powtarzaj ten krok, aż wszystkie punkty zostaną pokryte.

Algorytm Rittera działa w czasie $na$ $przestrzeni$ $wejściowych$ składających się z -wymiarowej bardzo wydajnym Jednak daje to tylko zgrubny wynik, który jest zwykle o 5% do 20% większy niż optymalny. ^{[ potrzebne źródło ]}

Przybliżenie oparte na zestawie rdzeni

Bădoiu i in. $}$ $varepsilon$ przybliżenie problemu ograniczającej sfery, gdzie przybliżenie , że skonstruowana kula ma co najwyżej $(1+\varepsilon)r$ $najmniejszym$ gdzie jest możliwym promieniem kuli ograniczającej.

Zestaw podstawowy to mały podzbiór, w którym rozszerzenie rozwiązania na podzbiór jest sferą $całego$ Zestaw podstawowy jest konstruowany stopniowo, dodając najdalszy punkt do zestawu w każdej iteracji.

Kumar i in. ulepszył ten algorytm aproksymacji tak, aby działał w czasie ${\ Displaystyle O ({\ Frac {nd} {\ epsilon}} + {\ Frac {1} {\ epsilon ^{4.5}}}\log {\frac {1}{\epsilon}})}$ .

Dokładny solwer Fischera

Fischera i in. (2003) zaproponowali rozwiązanie dokładne, chociaż w najgorszym przypadku algorytm nie ma wielomianowego czasu działania. Algorytm jest czysto kombinatoryczny i implementuje schemat przestawny podobny do metody simplex dla programowania liniowego , używanej wcześniej w niektórych heurystykach. Zaczyna się od dużej kuli, która obejmuje wszystkie punkty i stopniowo ją zmniejsza, aż nie można jej dalej zmniejszyć. Algorytm zawiera poprawne reguły zakończenia w przypadkach degeneracji, przeoczonych przez wcześniejszych autorów; i wydajną obsługę rozwiązań częściowych, co powoduje znaczne przyspieszenie. Autorzy zweryfikowali, że algorytm jest skuteczny w praktyce w niskich i średnio niskich (do 10 000) wymiarach i twierdzą, że nie wykazuje problemów ze stabilnością numeryczną w operacjach zmiennoprzecinkowych. Implementacja algorytmu w języku C++ jest dostępna jako projekt typu open source.

Optymalna kula punktów ekstremalnych

Larsson (2008) zaproponował metodę „sfery optymalnej punktów ekstremalnych” z kontrolowanym przybliżeniem prędkości do dokładności, aby rozwiązać problem sfery ograniczającej. Ta metoda działa poprzez pobranie zestawu $kierunkowych$ i rzutowanie wszystkich punktów na każdy wektor $;$ ${\ displaystyle s}$ służy jako zmienna kompromisu między szybkością a dokładnością. Do $się$ tych rzutów stosuje dokładny solver . Algorytm następnie iteruje po pozostałych punktach, jeśli takie istnieją, powiększając kulę, jeśli to konieczne. W przypadku dużych $.$ metoda jest o rząd wielkości szybsza niż metody dokładne, dając jednocześnie porównywalne wyniki Ma najgorszy przypadek czas ${\ Displaystyle O (sn)}$ .

Zobacz też

Linki zewnętrzne

Problem z najmniejszym otaczającym okręgiem - opisuje kilka algorytmów zamykania zbioru punktów, w tym algorytm czasu liniowego Megiddo