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 vértices. La más exterior es la envolvente convexa de los puntos y el resto se forman de la misma forma recursivamente . La capa más interna puede estar degenerada, consistiendo solo en 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 la construcción de las capas convexas mediante la búsqueda repetida de cascos convexos sería más lenta, es posible dividir cualquier conjunto de puntos en sus capas convexas en el tiempo . [1]
Una de las primeras aplicaciones de las capas convexas fue en 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, el número de capas convexas que rodean un punto determinado se denomina profundidad de pelado del casco convexo , y las propias capas convexas son los contornos de profundidad para esta noción de profundidad de datos. [5]
Las capas convexas se pueden usar 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 buscando 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]
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]
