Capas convexas

Las capas convexas de un conjunto de puntos y su intersección con un semiplano

En geometría computacional , las capas convexas de un conjunto de puntos en el plano euclidiano son una secuencia de polígonos convexos anidados que tienen los puntos como vértices. La más externa es la cáscara convexa de los puntos y el resto se forman de la misma forma recursivamente . La capa más interna puede estar degenerada y constar sólo de uno o dos puntos. ^[1] Al problema de construir capas convexas también se le ha llamado pelado de cebolla o descomposición de cebolla . ^[2]

Aunque construir las capas convexas encontrando repetidamente cascos convexos sería más lento, es posible dividir en el tiempo cualquier conjunto de puntos en sus capas convexas . ^[1] ${\displaystyle n}$ ${\displaystyle O(n\log n)}$

Una de las primeras aplicaciones de las capas convexas fue en estadística robusta , como una forma de identificar valores atípicos y medir la tendencia central de un conjunto de puntos muestrales. ^{[3] [4]} En este contexto, el número de capas convexas que rodean un punto dado se denomina profundidad de pelado del casco convexo , y las capas convexas mismas son los contornos de profundidad para esta noción de profundidad de datos. ^[5]

Las capas convexas se pueden utilizar como parte de una estructura de datos de informes de rango eficiente para enumerar todos los puntos en un semiplano de consulta . Los puntos en el semiplano de cada capa sucesiva se pueden encontrar mediante una búsqueda binaria para encontrar el punto más extremo en la dirección del semiplano y luego buscar secuencialmente desde allí. La cascada fraccional se puede utilizar para acelerar las búsquedas binarias, dando tiempo total de consulta para encontrar puntos de un conjunto de . ^[6] ${\displaystyle O(\log n+k)}$ ${\displaystyle k}$ ${\displaystyle n}$

Los puntos de una cuadrícula tienen capas convexas, ^[7] al igual que el mismo número de puntos uniformemente aleatorios dentro de cualquier forma convexa. ^[8] ${\displaystyle n\times n}$ ${\displaystyle \Theta (n^{4/3})}$

Referencias

1. Chazelle, Bernard (1985), "Sobre las capas convexas de un conjunto plano", IEEE Trans. inf. Teoría , 31 (4): 509–517, CiteSeerX  10.1.1.113.8709 , doi :10.1109/TIT.1985.1057060, SEÑOR  0798557
2. Löffler, Martín; Mulzer, Wolfgang (2014), "Uniones de cebollas: preprocesamiento de puntos imprecisos para una descomposición rápida de la cebolla", Journal of Computational Geometry , 5 (1): 1–13, arXiv : 1302.5328 , doi : 10.20382/jocg.v5i1a1, MR  3162956, S2CID  6679520.
3. Barnett, V. (1976), "El ordenamiento de datos multivariados", J. Roy. Estadístico. Soc. Ser. A , 139 (3): 318–355, doi : 10.2307/2344839, JSTOR  2344839, SEÑOR  0445726, S2CID  117008915
4. Eddy, WF (1982), "Convex Hull Peeling", COMPSTAT 1982, quinto simposio celebrado en Toulouse 1982, Physica-Verlag, págs. 42-47, doi :10.1007/978-3-642-51461-6_4, ISBN 978-3-7051-0002-2
5. Liu, Regina Y .; Parelius, Jesse M.; Singh, Kesar (1999), "Análisis multivariado por profundidad de datos: estadísticas descriptivas, gráficos e inferencia", Annals of Statistics , 27 (3): 783–858, doi : 10.1214/aos/1018031260 , MR  1724033
6. Chazelle, Bernardo ; Guibas, Leo J .; Lee, DT (1985), "El poder de la dualidad geométrica", BIT , 25 (1): 76–90, doi :10.1007/BF01934990, MR  0785806
7. Har-Peled, Sariel ; Lidický, Bernard (2013), "Peeling the grid", Revista SIAM de Matemáticas Discretas , 27 (2): 650–655, arXiv : 1302.3200 , doi :10.1137/120892660, MR  3040367, S2CID  15837161
8. Dalal, Ketan (2004), "Contando la cebolla", Algoritmos y estructuras aleatorias , 24 (2): 155–165, doi :10.1002/rsa.10114, MR  2035873, S2CID  10366666