Capas convexas

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] ${\estilo de visualización n}$ $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] $O(\log n+k)$ ${\estilo de visualización k}$ ${\estilo de visualización 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] $n\veces n$ $Estilo de visualización: \Theta (n^{4/3})}$

Referencias

^ ab 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
^ 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 .
^ 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
^ 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
^ 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
^ 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
^ 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
^ Dalal, Ketan (2004), "Contando la cebolla", Random Structures & Algorithms , 24 (2): 155–165, doi :10.1002/rsa.10114, MR 2035873, S2CID 10366666

[c85-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