Centerpoint (geometrie) - Centerpoint (geometry)
În statistică și geometrie computațională , noțiunea de punct central este o generalizare a mediei la datele din spațiul euclidian de dimensiuni superioare . Având în vedere un set de puncte într-un spațiu dimensional d , un punct central al mulțimii este un punct astfel încât orice hiperplan care trece prin acel punct împarte setul de puncte în două subseturi aproximativ egale: partea mai mică ar trebui să aibă cel puțin 1 / ( d + 1) fracție din puncte. Ca mediana, un punct central nu trebuie să fie unul dintre punctele de date. Fiecare set de puncte ne-gol (fără duplicate) are cel puțin un punct central.
Concepte conexe
Conceptele strâns legate sunt adâncimea Tukey a unui punct (numărul minim de puncte de eșantion dintr-o parte a unui hiperplan prin punct) și o mediană Tukey a unui set de puncte (un punct care maximizează adâncimea Tukey). Un punct central este un punct de adâncime cel puțin n / ( d + 1), iar o mediană Tukey trebuie să fie un punct central, dar nu orice punct central este o mediană Tukey. Ambii termeni sunt numiți după John Tukey .
Pentru o generalizare diferită a mediană a dimensiunilor superioare, a se vedea mediana geometrică .
Existenţă
O simplă dovadă a existenței unui punct central poate fi obținută folosind teorema lui Helly . Să presupunem că există n puncte și luați în considerare familia de spații închise care conțin mai mult de dn / ( d + 1) din puncte. Mai puține decât n / ( d + 1) puncte sunt excluse de la oricare dintre aceste jumătăți de spațiu, astfel încât intersecția oricărui subset de d + 1 din aceste jumătăți de spațiu trebuie să fie neatentă. După teorema lui Helly, rezultă că intersecția tuturor acestor spații pe jumătate trebuie să fie, de asemenea, neobișnuită. Orice punct din această intersecție este în mod necesar un punct central.
algoritmi
Pentru punctele din planul euclidian , un punct central poate fi construit în timp liniar . În orice dimensiune d , o mediană Tukey (și, prin urmare, și un punct central) poate fi construită în timp O ( n d - 1 + n log n ).
Un algoritm randomizat care înlocuiește în mod repetat seturi de d + 2 puncte de punctul Radon poate fi utilizat pentru a calcula o aproximare la un punct central al oricărui set de puncte, în sensul că adâncimea lui Tukey este liniară în dimensiunea setului de probă, într-o cantitate de timp care este polinomial atât în numărul de puncte cât și în dimensiune.
Referințe
Citatele
surse
- Chan, Timothy M. (2004), "Un algoritm randomizat optim pentru adâncimea maximă de Tukey", Proc. 15 ACM - SIAM Symp. pe Algoritmi discrete (SODA 2004) , p. 430–436.
- Clarkson, Kenneth L .; Eppstein, David ; Miller, Gary L .; Sturtivant, Carl; Teng, Shang-Hua (septembrie 1996), „Aproximarea punctelor centrale cu puncte Radon iteratate” (PDF) , Int. J. Geometrie și aplicații computationale , 6 (3): 357–377, MR 1409651.
- Edelsbrunner, Herbert (1987), Algoritmi în geometrie combinată , Berlin: Springer-Verlag, ISBN 0-387-13722-X.
- Jadhav, S.; Mukhopadhyay, A. (1994), "o calculare a unui set Centerpoint planar finit de puncte în timp liniar", discretă și computațională Geometrie , 12 (1): 291-312, doi : 10.1007 / BF02574382.