Punkt środkowy (geometria)

W statystyce i geometrii obliczeniowej pojęcie punktu środkowego jest uogólnieniem mediany na dane w wielowymiarowej przestrzeni euklidesowej . Biorąc pod uwagę zbiór punktów w d -wymiarowej, środkiem zbioru jest taki punkt, że każda hiperpłaszczyzna przechodząca przez ten punkt dzieli zbiór punktów na dwa w przybliżeniu równe podzbiory: mniejsza część powinna mieć co najmniej 1/( d + 1) ułamek punktów. Podobnie jak mediana, punkt środkowy nie musi być jednym z punktów danych. Każdy niepusty zbiór punktów (bez duplikatów) ma co najmniej jeden punkt środkowy.

Pojęcia pokrewne

Ściśle powiązane koncepcje to głębokość punktu Tukeya (minimalna liczba punktów próbkowania po jednej stronie hiperpłaszczyzny przechodzącej przez punkt) i mediana Tukeya zbioru punktów (punkt maksymalizujący głębokość Tukeya). Punkt środkowy jest punktem o głębokości co najmniej n / ( d + 1), a mediana Tukeya musi być punktem środkowym, ale nie każdy punkt środkowy jest medianą Tukeya. Oba terminy zostały nazwane na cześć Johna Tukeya .

Aby zapoznać się z innym uogólnieniem mediany na wyższe wymiary, zobacz medianę geometryczną .

Istnienie

Prosty dowód na istnienie punktu środkowego można uzyskać za pomocą twierdzenia Helly'ego . Załóżmy, że istnieje n punktów i rozważmy rodzinę zamkniętych półprzestrzeni , które zawierają więcej niż dn /( d + 1) punktów. Mniej niż n / ( d + 1) punktów jest wykluczonych z dowolnej z tych półprzestrzeni, więc przecięcie dowolnego podzbioru d + 1 tych półprzestrzeni musi być niepuste. Z twierdzenia Helly'ego wynika, że ​​przecięcie wszystkich tych półprzestrzeni również musi być niepuste. Każdy punkt na tym przecięciu jest koniecznie środkiem.

Algorytmy

Dla punktów na płaszczyźnie euklidesowej punkt środkowy można zbudować w czasie liniowym . W dowolnym wymiarze d mediana Tukeya (a zatem także punkt środkowy) może być skonstruowana w czasie O( n ^{d - 1} + n log n ).

Losowy algorytm , który wielokrotnie zastępuje zestawy punktów d + 2 ich punktem Radona , może być użyty do obliczenia przybliżenia do punktu środkowego dowolnego zestawu punktów, w tym sensie, że jego głębokość Tukeya jest liniowa w rozmiarze zestawu próbek, w ilości czas, który jest wielomianem zarówno pod względem liczby punktów, jak i wymiaru.

Źródła

• Chan, Timothy M. (2004), „Optymalny algorytm z randomizacją dla maksymalnej głębokości Tukeya”, Proc. 15 Symp. ACM – SIAM w sprawie algorytmów dyskretnych (SODA 2004) , s. 430–436 .
•   Clarkson, Kenneth L .; Eppstein, David ; Miller, Gary L .; Sturtivant, Carl; Teng, Shang-Hua (wrzesień 1996), „Przybliżanie punktów środkowych z iterowanymi punktami radonu” (PDF) , International Journal of Computational Geometry & Applications , 6 (3): 357–377, MR 1409651 .
•   Edelsbrunner, Herbert (1987), Algorytmy w geometrii kombinatorycznej , Berlin: Springer-Verlag, ISBN 0-387-13722-X .
• Jadhav, S.; Mukhopadhyay, A. (1994), „Obliczanie punktu środkowego skończonego płaskiego zestawu punktów w czasie liniowym”, Discrete and Computational Geometry , 12 (1): 291–312, doi : 10.1007 / BF02574382 .