Centerpoint (geometria) - Centerpoint (geometry)

In statistica e geometria computazionale , la nozione di punto centrale è una generalizzazione della mediana per i dati in alto-dimensionale spazio euclideo . Dato un insieme di punti d spazio dimensionale, un punto centrale del set è un punto tale che qualsiasi iperpiano che passa attraverso quel punto divide l'insieme di punti in due sottoinsiemi quasi uguali: la parte più piccola dovrebbe avere almeno un 1 / ( d  + 1) frazione dei punti. Come la mediana, un punto centrale non deve essere uno dei punti di dati. Ogni insieme non vuoto di punti (senza duplicati) ha almeno un punto centrale.

concetti correlati

Concetti strettamente correlati sono la profondità Tukey di un punto (il numero minimo di punti campione su un lato di un iperpiano attraverso il punto) e una mediana Tukey di un set point (punto di massimizzare la profondità Tukey). Un punto centrale è un punto della profondità almeno n / ( d  + 1), e una mediana Tukey deve essere un punto centrale, ma non ogni punto centrale è una mediana Tukey. Entrambi i termini sono chiamati dopo John Tukey .

Per una diversa generalizzazione della mediana di dimensioni superiori, vedi mediana geometrica .

Esistenza

Una semplice prova dell'esistenza di un punto centrale può essere ottenuto utilizzando il teorema di Helly . Supponiamo che ci siano n punti, e considerano la famiglia di chiusi semispazi che contengono più di dn / ( D  + 1) dei punti. Meno di n / ( d  + 1) punti sono esclusi da uno qualsiasi di questi semispazi, quindi l'intersezione di qualsiasi sottoinsieme di d  + 1 di questi semispazi devono essere non vuoto. Per il teorema di Helly, ne consegue che l'intersezione di tutte queste semispazi deve anche essere non vuota. Qualsiasi punto in questa intersezione è necessariamente un punto centrale.

algoritmi

Per i punti nel piano euclideo , un punto centrale può essere costruito in tempo lineare . In qualsiasi dimensione d , una mediana Tukey (e quindi anche un punto centrale) possono essere costruiti in tempo O ( n ^{D  - 1}  +  n  log  n ).

Un algoritmo randomizzato che sostituisce ripetutamente insiemi di d  + 2 punti dal loro punto radon può essere utilizzato per calcolare un'approssimazione ad un punto centrale di ogni set point, nel senso che la sua profondità Tukey è lineare nella dimensione campionario, in una quantità di tempo che è polinomiale sia nel numero di punti e la dimensione.

Riferimenti

citazioni

fonti

• Chan, Timothy M. (2004), "Un algoritmo randomizzato ottimale per profondità massima Tukey", Proc. 15 ACM-SIAM Symp. su discreti algoritmi (SODA 2004) , pp. 430-436.
• Clarkson, Kenneth L. ; Eppstein, David ; Miller, Gary L. ; Sturtivant, Carl; Teng, Shang-Hua (settembre 1996), "Approssimando punti centrali con punti radon iterate" (PDF) , Int. J. Computational Geometry & Applications , 6 (3): 357-377, MR  1.409.651.
• Edelsbrunner, Herbert (1987), algoritmi di Geometria Combinatoria , Berlin: Springer-Verlag, ISBN  0-387-13722-X.
• Jadhav, S .; Mukhopadhyay, A. (1994), "Calcolo di un punto centrale di un insieme planare finito di punti nel tempo lineare", Discrete e geometria computazionale , 12 (1): 291-312, doi : 10.1007 / BF02574382.