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 sus vértices. La más externa es la envoltura convexa de los puntos y el resto se forman de la misma manera de forma recursiva . La capa más interna puede ser degenerada, consistiendo solo en uno o dos puntos. ^[1] El problema de construir capas convexas también se ha denominado pelado de cebolla o descomposición de cebolla . ^[2]

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

Una aplicación temprana de las capas convexas fue en las estadísticas robustas , como una forma de identificar valores atípicos y medir la tendencia central de un conjunto de puntos de muestra. ^{[3] [4]} En este contexto, la cantidad de capas convexas que rodean un punto dado se denomina profundidad de pelado de la envoltura convexa , y las capas convexas en sí 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í. Se puede utilizar la cascada fraccionaria para acelerar las búsquedas binarias, lo que da un tiempo de consulta total 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. Theory , 31 (4): 509–517, CiteSeerX  10.1.1.113.8709 , doi :10.1109/TIT.1985.1057060, MR  0798557
2. Löffler, Maarten; Mulzer, Wolfgang (2014), "Uniones de cebollas: preprocesamiento de puntos imprecisos para una descomposición rápida de cebollas", 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. Statist. Soc. Ser. A , 139 (3): 318–355, doi :10.2307/2344839, JSTOR  2344839, MR  0445726, S2CID  117008915
4. Eddy, WF (1982), "Convex Hull Peeling", COMPSTAT 1982 5th Symposium 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, Bernard ; 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), "Pelar la cuadrícula", SIAM Journal on Discrete Mathematics , 27 (2): 650–655, arXiv : 1302.3200 , doi :10.1137/120892660, MR  3040367, S2CID  15837161
8. Dalal, Ketan (2004), "Contando la cebolla", Random Structures & Algorithms , 24 (2): 155–165, doi :10.1002/rsa.10114, MR  2035873, S2CID  10366666