Punto central (geometría)

En estadística y geometría computacional , el concepto de punto central es una generalización de la mediana a datos en el espacio euclidiano de dimensiones superiores . Dado un conjunto de puntos en un espacio d -dimensional, un punto central es aquel tal que cualquier hiperplano que pase por él divide el conjunto de puntos en dos subconjuntos aproximadamente iguales: la parte menor debe contener al menos una fracción de 1/( d  +  1) de los puntos. Al igual que la mediana, un punto central no tiene por qué ser uno de los puntos de datos. Todo conjunto de puntos no vacío (sin duplicados) tiene al menos un punto central.

Conceptos estrechamente relacionados son la profundidad de Tukey de un punto (el número mínimo de puntos de muestra a un lado de un hiperplano que pasa por el punto) y la mediana de Tukey de un conjunto de puntos (un punto que maximiza la profundidad de Tukey). Un punto central es un punto con una profundidad de al menos n / ( d  +  1), y una mediana de Tukey debe ser un punto central, pero no todo punto central es una mediana de Tukey. Ambos términos reciben su nombre de John Tukey .

Para una generalización diferente de la mediana a dimensiones superiores, consulte la mediana geométrica .

Una demostración sencilla de la existencia de un centro se puede obtener utilizando el teorema de Helly . Supongamos que hay n puntos y consideremos la familia de semiplanos cerrados que contienen más de dn / ( d  +  1) puntos. Menos de n / ( d  +  1) puntos están excluidos de cualquiera de estos semiplanos, por lo que la intersección de cualquier subconjunto de d  +  1 de estos semiplanos debe ser no vacía. Por el teorema de Helly, se deduce que la intersección de todos estos semiplanos también debe ser no vacía. Cualquier punto en esta intersección es necesariamente un centro.

Para puntos en el plano euclidiano , se puede construir un punto central en tiempo lineal . ^{[ 1 ]} En cualquier dimensión d , se puede construir una mediana de Tukey (y por lo tanto también un punto central) en tiempo O( n ^{d − 1}    + n log n ). ^{[ 2 ]}   

Se puede utilizar un algoritmo aleatorio que reemplaza repetidamente conjuntos de d  +  2 puntos por su punto de Radon para calcular una aproximación al punto central de cualquier conjunto de puntos, en el sentido de que su profundidad de Tukey es lineal en el tamaño del conjunto de muestra, en un tiempo polinomial en la dimensión. ^{[ 3 ] [ 4 ]}