En geometría , el casco convexo o sobre convexo o cierre convexo de una forma es el conjunto convexo más pequeño que lo contiene. El casco convexo puede definirse como la intersección de todos los conjuntos convexos que contienen un subconjunto dado de un espacio euclidiano o, de manera equivalente, como el conjunto de todas las combinaciones convexas de puntos del subconjunto. Para un subconjunto delimitado del avión, el casco convexo se puede visualizar como la forma encerrada por una banda elástica estirada alrededor del subconjunto.
Los cascos convexos de los conjuntos abiertos están abiertos y los cascos convexos de los conjuntos compactos son compactos. Todo conjunto convexo compacto es el casco convexo de sus puntos extremos . El operador de casco convexo es un ejemplo de operador de cierre , y cada antimatroide se puede representar aplicando este operador de cierre a conjuntos finitos de puntos. Los problemas algorítmicos de encontrar el casco convexo de un conjunto finito de puntos en el plano u otros espacios euclidianos de baja dimensión, y su problema dual de intersección de medios espacios , son problemas fundamentales de geometría computacional . Pueden resolverse a tiempopara conjuntos de puntos bidimensionales o tridimensionales y, en el tiempo, igualar la complejidad de salida del peor de los casos dada por el teorema del límite superior en dimensiones superiores.
Además de los conjuntos de puntos finitos, los cascos convexos también se han estudiado para polígonos simples , movimiento browniano , curvas espaciales y epígrafes de funciones . Los cascos convexos tienen amplias aplicaciones en matemáticas, estadística, optimización combinatoria, economía, modelado geométrico y etología. Las estructuras relacionadas incluyen el casco convexo ortogonal , las capas convexas , la triangulación de Delaunay y el diagrama de Voronoi , y el cráneo convexo .
Definiciones
Un conjunto de puntos en un espacio euclidiano se define como convexo si contiene los segmentos de línea que conectan cada par de sus puntos. El casco convexo de un conjunto dadopuede definirse como [1]
- El conjunto convexo mínimo (único) que contiene
- La intersección de todos los conjuntos convexos que contienen
- El conjunto de todas las combinaciones convexas de puntos en
- La unión de todos los simples con vértices en
Para conjuntos delimitados en el plano euclidiano, no todos en una línea, el límite del casco convexo es la curva cerrada simple con un perímetro mínimo que contiene. Uno puede imaginarse estirando una goma elástica para que rodee todo el conjunto.y luego soltándolo, permitiendo que se contraiga; cuando se tensa, encierra el casco convexo de. [2] Esta formulación no se generaliza inmediatamente a dimensiones superiores: para un conjunto finito de puntos en un espacio tridimensional, una vecindad de un árbol de expansión de los puntos los encierra con una superficie arbitrariamente pequeña, más pequeña que la superficie del convexo. cáscara. [3] Sin embargo, en dimensiones más altas, las variantes del problema del obstáculo de encontrar una superficie de energía mínima por encima de una forma dada pueden tener el casco convexo como solución. [4]
Para objetos en tres dimensiones, la primera definición establece que el casco convexo es el volumen delimitador convexo más pequeño posible de los objetos. La definición que usa intersecciones de conjuntos convexos puede extenderse a geometría no euclidiana , y la definición que usa combinaciones convexas puede extenderse desde espacios euclidianos a espacios vectoriales reales arbitrarios o espacios afines ; los cascos convexos también pueden generalizarse de una manera más abstracta, a matroides orientados . [5]
Equivalencia de definiciones
No es obvio que la primera definición tenga sentido: ¿por qué debería existir un conjunto convexo mínimo único que contenga , para cada ? Sin embargo, la segunda definición, la intersección de todos los conjuntos convexos que contienen, está bien definido. Es un subconjunto de todos los demás conjuntos convexos. eso contiene , porque se incluye entre los conjuntos que se cruzan. Por lo tanto, es exactamente el conjunto convexo mínimo único que contiene. Por tanto, las dos primeras definiciones son equivalentes. [1]
Cada conjunto convexo que contiene debe (asumiendo que es convexo) contener todas las combinaciones convexas de puntos en , por lo que el conjunto de todas las combinaciones convexas está contenido en la intersección de todos los conjuntos convexos que contienen . Por el contrario, el conjunto de todas las combinaciones convexas es en sí mismo un conjunto convexo que contiene, por lo que también contiene la intersección de todos los conjuntos convexos que contienen , y por lo tanto la segunda y tercera definiciones son equivalentes. [6]
De hecho, de acuerdo con el teorema de Carathéodory , si es un subconjunto de un -espacio euclidiano dimensional, toda combinación convexa de un número finito de puntos de es también una combinación convexa de como máximo puntos en . El conjunto de combinaciones convexas de un-tupla de puntos es un simplex ; en el plano es un triángulo y en el espacio tridimensional es un tetraedro. Por lo tanto, toda combinación convexa de puntos de pertenece a un simplex cuyos vértices pertenecen a , y la tercera y cuarta definiciones son equivalentes. [6]
Cascos superiores e inferiores
En dos dimensiones, el casco convexo a veces se divide en dos partes, el casco superior y el casco inferior, extendiéndose entre los puntos más a la izquierda y más a la derecha del casco. De manera más general, para cascos convexos en cualquier dimensión, se puede dividir el límite del casco en puntos que miran hacia arriba (puntos para los cuales un rayo hacia arriba está separado del casco), puntos que miran hacia abajo y puntos extremos. Para los cascos tridimensionales, las partes del límite que miran hacia arriba y hacia abajo forman discos topológicos. [7]
Propiedades topologicas
Cascos cerrados y abiertos
El casco convexo cerrado de un conjunto es el cierre del casco convexo, y el casco convexo abierto es el interior (o en algunas fuentes el interior relativo ) del casco convexo. [8]
El casco convexo cerrado de es la intersección de todos los semiespacios cerrados que contienen. Si el casco convexo deya es un conjunto cerrado en sí mismo (como sucede, por ejemplo, sies un conjunto finito o más generalmente un conjunto compacto ), entonces es igual al casco convexo cerrado. Sin embargo, una intersección de medios espacios cerrados está cerrada en sí misma, por lo que cuando un casco convexo no está cerrado, no se puede representar de esta manera. [9]
Si el casco convexo abierto de un conjunto es -dimensional, entonces cada punto del casco pertenece a un casco convexo abierto de como máximo puntos de . Los conjuntos de vértices de un cuadrado, octaedro regular o politopo cruzado de dimensiones superiores proporcionan ejemplos donde exactamentese necesitan puntos. [10]
Preservación de propiedades topológicas.
Topológicamente, el casco convexo de un conjunto abierto siempre está abierto en sí mismo, y el casco convexo de un conjunto compacto es siempre compacto en sí mismo. Sin embargo, existen conjuntos cerrados para los que el casco convexo no está cerrado. [11] Por ejemplo, el conjunto cerrado
(el conjunto de puntos que se encuentran sobre o encima de la bruja de Agnesi ) tiene el semiplano superior abierto como su casco convexo. [12]
La compacidad de los cascos convexas de conjuntos compactos, en espacios euclídeos de dimensión finita, se generaliza por el teorema Kerin-Smulian , según la cual la envolvente convexa cerrada de un subconjunto débilmente compacto de un espacio de Banach (un subconjunto que es compacto bajo la débil topología ) es débilmente compacto. [13]
Puntos extremos
Un punto extremo de un conjunto convexo es un punto del conjunto que no se encuentra en ningún segmento de línea abierto entre otros dos puntos del mismo conjunto. Para un casco convexo, cada punto extremo debe ser parte del conjunto dado, porque de lo contrario no puede formarse como una combinación convexa de puntos dados. Según el teorema de Kerin-Milman , todo conjunto convexo compacto en un espacio euclidiano (o más generalmente en un espacio vectorial topológico localmente convexo ) es el casco convexo de sus puntos extremos. [14] Sin embargo, esto puede no ser cierto para conjuntos convexos que no son compactos; por ejemplo, todo el plano euclidiano y la bola unitaria abierta son convexos, pero ninguno tiene puntos extremos. La teoría de Choquet extiende esta teoría desde combinaciones finitas convexas de puntos extremos hasta combinaciones infinitas (integrales) en espacios más generales. [15]
Propiedades geométricas y algebraicas
Operador de cierre
El operador de casco convexo tiene las propiedades características de un operador de cierre : [16]
- Es extenso , lo que significa que el casco convexo de cada conjunto es un superconjunto de .
- No es decreciente , lo que significa que, por cada dos conjuntos y con , el casco convexo de es un subconjunto del casco convexo de .
- Es idempotente , lo que significa que para cada, el casco convexo del casco convexo de es el mismo que el casco convexo de .
Cuando se aplica a un conjunto finito de puntos, es el operador de cierre de un antimatroide , el antimatroide de bombardeo del conjunto de puntos. Cada antimatroide puede representarse de esta manera por cascos convexos de puntos en un espacio euclidiano de dimensión suficientemente alta. [17]
Suma de Minkowski
Las operaciones de construir el casco convexo y tomar la suma de Minkowski se conmutan entre sí, en el sentido de que la suma de Minkowski de cascos convexos de conjuntos da el mismo resultado que el casco convexo de la suma de Minkowski de los mismos conjuntos. Esto proporciona un paso hacia el teorema de Shapley-Folkman que limita la distancia de una suma de Minkowski desde su casco convexo. [18]
Dualidad proyectiva
La operación dual proyectiva para construir el casco convexo de un conjunto de puntos es construir la intersección de una familia de semiespacios cerrados que contienen todos el origen (o cualquier otro punto designado). [19]
Casos especiales
Conjuntos de puntos finitos
El casco convexo de un conjunto de puntos finitos forma un polígono convexo cuando, o más generalmente un politopo convexo en. Cada punto extremo del casco se llama vértice y (según el teorema de Kerin-Milman) cada politopo convexo es el casco convexo de sus vértices. Es el politopo convexo único cuyos vértices pertenecen a y que encierra todo . [2] Para conjuntos de puntos en posición general , el casco convexo es un politopo simplicial . [20]
De acuerdo con el teorema del límite superior , el número de caras del casco convexo de puntos en -el espacio euclidiano dimensional es . [21] En particular, en dos y tres dimensiones, el número de caras es como máximo lineal en. [22]
Polígonos simples
El casco convexo de un polígono simple encierra el polígono dado y está dividido por él en regiones, una de las cuales es el polígono mismo. Las otras regiones, delimitadas por una cadena poligonal del polígono y un solo borde convexo del casco, se denominan bolsillos . Calcular la misma descomposición de forma recursiva para cada bolsillo forma una descripción jerárquica de un polígono dado llamado árbol de diferencias convexas . [23] Reflejar un bolsillo a lo largo de su borde convexo del casco expande el polígono simple dado en un polígono con el mismo perímetro y área más grande, y el teorema de Erdős-Nagy establece que este proceso de expansión eventualmente termina. [24]
movimiento browniano
La curva generada por el movimiento browniano en el plano, en cualquier momento fijo, tiene una probabilidad 1 de tener un casco convexo cuyo límite forma una curva continuamente diferenciable . Sin embargo, para cualquier ángulo en el rango , habrá momentos durante el movimiento browniano en los que la partícula en movimiento toque el límite del casco convexo en un punto de ángulo . La dimensión de Hausdorff de este conjunto de momentos excepcionales es (con alta probabilidad). [25]
Curvas espaciales
Para el casco convexo de una curva espacial o un conjunto finito de curvas espaciales en posición general en un espacio tridimensional, las partes del límite alejadas de las curvas son superficies desarrollables y regladas . [26] Los ejemplos incluyen el oloide , el casco convexo de dos círculos en planos perpendiculares, cada uno pasando por el centro del otro, [27] el esférico , el casco convexo de dos semicírculos en planos perpendiculares con un centro común, y formas D, las formas convexas obtenidas del teorema de unicidad de Alexandrov para una superficie formada al pegar dos conjuntos convexos planos de igual perímetro. [28]
Funciones
El casco convexo o envolvente convexa inferior de una función.en un espacio vectorial real es la función cuyo epígrafe es el casco convexo inferior del epígrafe de. Es la única función convexa máxima mayorizada por. [29] La definición puede extenderse al casco convexo de un conjunto de funciones (obtenidas del casco convexo de la unión de sus epígrafes, o equivalentemente de su mínimo puntual ) y, en esta forma, es dual a la operación conjugada convexa . [30]
Cálculo
En geometría computacional , se conocen varios algoritmos para calcular el casco convexo para un conjunto finito de puntos y para otros objetos geométricos. Calcular el casco convexo significa construir una representación inequívoca y eficiente de la forma convexa requerida. Las representaciones de salida que se han considerado para cascos convexos de conjuntos de puntos incluyen una lista de desigualdades lineales que describen las facetas del casco, un gráfico no dirigido de facetas y sus adyacencias, o la celosía de cara completa del casco. [31] En dos dimensiones, puede ser más sencillo enumerar los puntos que son vértices, en su orden cíclico alrededor del casco. [2]
Para cascos convexos en dos o tres dimensiones, la complejidad de los algoritmos correspondientes generalmente se estima en términos de , el número de puntos de entrada, y , el número de puntos en el casco convexo, que puede ser significativamente menor que . Para cascos de dimensiones superiores, el número de caras de otras dimensiones también puede entrar en el análisis. El escaneo de Graham puede calcular el casco convexo de puntos en el plano en el tiempo . Para puntos en dos y tres dimensiones, se conocen algoritmos sensibles a la salida más complicados que calculan el casco convexo en el tiempo.. Estos incluyen el algoritmo de Chan y el algoritmo de Kirkpatrick-Seidel . [32] Para dimensiones, el tiempo para calcular el casco convexo es , haciendo coincidir la complejidad de salida del problema en el peor de los casos. [33] El casco convexo de un polígono simple en el plano se puede construir en tiempo lineal . [34]
Las estructuras de datos dinámicas del casco convexo se pueden utilizar para realizar un seguimiento del casco convexo de un conjunto de puntos sometidos a inserciones y eliminaciones de puntos, [35] y las estructuras cinéticas del casco convexo pueden realizar un seguimiento del casco convexo para los puntos que se mueven continuamente. [36] La construcción de cascos convexos también sirve como una herramienta, un bloque de construcción para una serie de otros algoritmos geométricos computacionales, como el método de calibradores giratorios para calcular el ancho y el diámetro de un conjunto de puntos. [37]
Estructuras relacionadas
Varias otras formas se pueden definir a partir de un conjunto de puntos de manera similar al casco convexo, como el superconjunto mínimo con alguna propiedad, la intersección de todas las formas que contienen los puntos de una familia de formas dada, o la unión de todas las combinaciones de puntos por un cierto tipo de combinación. Por ejemplo:
- El casco afín es el subespacio afín más pequeño de un espacio euclidiano que contiene un conjunto dado, o la unión de todas las combinaciones afines de puntos del conjunto. [38]
- El casco lineal es el subespacio lineal más pequeño de un espacio vectorial que contiene un conjunto dado, o la unión de todas las combinaciones lineales de puntos en el conjunto. [38]
- El casco cónico o casco positivo de un subconjunto de un espacio vectorial es el conjunto de todas las combinaciones positivas de puntos en el subconjunto. [38]
- El casco visual de un objeto tridimensional, con respecto a un conjunto de puntos de vista, consta de los puntos tal que cada rayo desde un punto de vista a través se cruza con el objeto. De manera equivalente es la intersección de los conos (no convexos) generados por el contorno del objeto con respecto a cada punto de vista. Se utiliza en la reconstrucción 3D como la forma más grande que podría tener los mismos contornos desde los puntos de vista dados. [39]
- El casco circular o casco alfa de un subconjunto del plano es la intersección de todos los discos con un radio determinado. que contienen el subconjunto. [40]
- El casco relativamente convexo de un subconjunto de un polígono simple bidimensional es la intersección de todos los superconjuntos relativamente convexos, donde un conjunto dentro del mismo polígono es relativamente convexo si contiene la geodésica entre dos de sus puntos. [41]
- El casco ortogonal convexo o rectilíneo convexo es la intersección de todos los superconjuntos ortogonalmente convexos y conectados, donde un conjunto es ortogonalmente convexo si contiene todos los segmentos paralelos al eje entre pares de sus puntos. [42]
- El casco convexo ortogonal es un caso especial de una construcción mucho más general, el casco hiperconvexo , que puede considerarse como el espacio métrico inyectivo más pequeño que contiene los puntos de un espacio métrico dado . [43]
- El casco holomórficamente convexo es una generalización de conceptos similares a variedades analíticas complejas , obtenida como una intersección de conjuntos de subniveles de funciones holomórficas que contienen un conjunto dado. [44]
La triangulación de Delaunay de un conjunto de puntos y su dual , el diagrama de Voronoi , están matemáticamente relacionados con cascos convexos: la triangulación de Delaunay de un conjunto de puntos en puede verse como la proyección de un casco convexo en [45] Las formas alfa de un conjunto de puntos finitos dan una familia anidada de objetos geométricos (no convexos) que describen la forma de un conjunto de puntos en diferentes niveles de detalle. Cada una de las formas alfa es la unión de algunas de las características de la triangulación de Delaunay, seleccionadas comparando su circunradio con el parámetro alfa. El conjunto de puntos en sí forma un punto final de esta familia de formas, y su casco convexo forma el otro punto final. [40] Las capas convexas de un conjunto de puntos son una familia anidada de polígonos convexos, el más externo de los cuales es el casco convexo, con las capas internas construidas recursivamente a partir de los puntos que no son vértices del casco convexo. [46]
El cráneo convexo de un polígono es el polígono convexo más grande que contiene. Se puede encontrar en tiempo polinomial , pero el exponente del algoritmo es alto. [47]
Aplicaciones
Los cascos convexos tienen amplias aplicaciones en muchos campos. Dentro de las matemáticas, los cascos convexos se utilizan para estudiar polinomios , valores propios de matrices y elementos unitarios , y varios teoremas en geometría discreta implican cascos convexos. Se utilizan en estadísticas sólidas como el contorno más externo de la profundidad de Tukey , son parte de la visualización del gráfico de bolsa de datos bidimensionales y definen conjuntos de riesgos de reglas de decisión aleatorias . Los cascos convexos de vectores indicadores de soluciones a problemas combinatorios son fundamentales para la optimización combinatoria y la combinatoria poliédrica . En economía, los cascos convexos se pueden utilizar para aplicar métodos de convexidad en economía a mercados no convexos. En el modelado geométrico, las curvas de Bézier de la propiedad del casco convexo ayudan a encontrar sus cruces, y los cascos convexos son parte de la medición de los cascos de los barcos. Y en el estudio del comportamiento animal, los cascos convexos se utilizan en una definición estándar del área de distribución .
Matemáticas
Los polígonos de Newton de polinomios univariados y los politopos de Newton de polinomios multivariados son cascos convexos de puntos derivados de los exponentes de los términos en el polinomio y se pueden utilizar para analizar el comportamiento asintótico del polinomio y las valoraciones de sus raíces. [48] Los polinomios y cascos convexos también se juntan en el teorema de Gauss-Lucas , según el cual las raíces de la derivada de un polinomio se encuentran todas dentro del casco convexo de las raíces del polinomio. [49]
En el análisis espectral , el rango numérico de una matriz normal es el casco convexo de sus valores propios . [50] El teorema de Russo-Dye describe los cascos convexos de elementos unitarios en un C * -álgebra . [51] En geometría discreta , tanto el teorema de Radon y el teorema de Tverberg preocupación la existencia de las particiones de los conjuntos de puntos en subconjuntos con la intersección de los cascos convexas. [52]
Las definiciones de un conjunto convexo como que contiene segmentos de línea entre sus puntos, y de un casco convexo como la intersección de todos los superconjuntos convexos, se aplican tanto a los espacios hiperbólicos como a los espacios euclidianos. Sin embargo, en el espacio hiperbólico, también es posible considerar los cascos convexos de conjuntos de puntos ideales , puntos que no pertenecen al espacio hiperbólico en sí, pero que se encuentran en el límite de un modelo de ese espacio. Los límites de los cascos convexos de los puntos ideales del espacio hiperbólico tridimensional son análogos a las superficies regladas en el espacio euclidiano, y sus propiedades métricas juegan un papel importante en la conjetura de geometrización en la topología de baja dimensión . [53] Los cascos convexos hiperbólicos también se han utilizado como parte del cálculo de triangulaciones canónicas de variedades hiperbólicas , y se han aplicado para determinar la equivalencia de nudos . [54]
Véase también la sección sobre movimiento browniano para la aplicación de cascos convexos a este tema, y la sección sobre curvas espaciales para su aplicación a la teoría de superficies desarrollables .
Estadísticas
En estadísticas sólidas , el casco convexo proporciona uno de los componentes clave de un gráfico de bolsas , un método para visualizar la dispersión de puntos de muestra bidimensionales. Los contornos de la profundidad de Tukey forman una familia anidada de conjuntos convexos, con el casco convexo más externo, y el gráfico de bolsas también muestra otro polígono de esta familia anidada, el contorno del 50% de profundidad. [55]
En la teoría de la decisión estadística , el conjunto de riesgos de una regla de decisión aleatoria es el casco convexo de los puntos de riesgo de sus reglas de decisión deterministas subyacentes. [56]
Optimización combinatoria
En optimización combinatoria y combinatoria poliédrica , los objetos centrales de estudio son los cascos convexos de vectores indicadores de soluciones a un problema combinatorio. Si se pueden encontrar las facetas de estos politopos, describiendo los politopos como intersecciones de medios espacios, entonces se pueden usar algoritmos basados en programación lineal para encontrar soluciones óptimas. [57] En la optimización multiobjetivo , también se utiliza un tipo diferente de casco convexo, el casco convexo de los vectores de peso de las soluciones. Se puede maximizar cualquier combinación cuasiconvexa de pesos encontrando y verificando cada vértice convexo del casco, a menudo de manera más eficiente que verificando todas las soluciones posibles. [58]
Ciencias económicas
En el modelo Arrow-Debreu de equilibrio económico general , se supone que los agentes tienen conjuntos presupuestarios convexos y preferencias convexas . Estos supuestos de convexidad en economía se pueden utilizar para demostrar la existencia de un equilibrio. Cuando los datos económicos reales no son convexos , pueden hacerse convexos tomando cascos convexos. El teorema de Shapley-Folkman se puede utilizar para demostrar que, para mercados grandes, esta aproximación es precisa y conduce a un "cuasi-equilibrio" para el mercado no convexo original. [59]
Modelado geométrico
En el modelado geométrico , una de las propiedades clave de una curva de Bézier es que se encuentra dentro del casco convexo de sus puntos de control. Esta denominada "propiedad de casco convexo" se puede utilizar, por ejemplo, para detectar rápidamente intersecciones de estas curvas. [60]
En la geometría del diseño de barcos y barcos, la circunferencia de la cadena es una medida del tamaño de un barco de vela, definida utilizando el casco convexo de una sección transversal del casco del barco. Se diferencia de la circunferencia de la piel , el perímetro de la propia sección transversal, excepto en los barcos y barcos que tienen un casco convexo. [61]
Etología
El casco convexo se conoce comúnmente como el polígono convexo mínimo en etología , el estudio del comportamiento animal, donde es un enfoque clásico, aunque quizás simplista, para estimar el área de distribución de un animal en función de los puntos donde se ha observado al animal. [62] Los valores atípicos pueden hacer que el polígono convexo mínimo sea excesivamente grande, lo que ha motivado enfoques relajados que contienen solo un subconjunto de las observaciones, por ejemplo, eligiendo una de las capas convexas que esté cerca de un porcentaje objetivo de las muestras, [63] o en el método de casco convexo local combinando cascos convexos de vecindarios de puntos. [64]
Física cuántica
En física cuántica , el espacio de estados de cualquier sistema cuántico, el conjunto de todas las formas en que se puede preparar el sistema, es un casco convexo cuyos puntos extremos son operadores positivos semidefinidos conocidos como estados puros y cuyos puntos interiores se denominan estados mixtos. [65] El teorema de Schrödinger-HJW demuestra que, de hecho, cualquier estado mixto puede escribirse como una combinación convexa de estados puros de múltiples formas. [66]
Historia
El casco inferior convexo de puntos en el plano aparece, en la forma de un polígono de Newton, en una carta de Isaac Newton a Henry Oldenburg en 1676. [67] El término "casco convexo" en sí mismo aparece ya en la obra de Garrett Birkhoff ( 1935 ), y el término correspondiente en alemán aparece antes, por ejemplo, en la revisión de Hans Rademacher de Kőnig ( 1922 ). Otros términos, como "envolvente convexa", también se utilizaron en este período de tiempo. [68] Para 1938, según Lloyd Dines , el término "casco convexo" se había convertido en estándar; Dines agrega que encuentra el término desafortunado, porque el significado coloquial de la palabra "casco" sugeriría que se refiere a la superficie de una forma, mientras que el casco convexo incluye el interior y no solo la superficie. [69]
Notas
- ↑ a b Rockafellar (1970) , p. 12.
- ^ a b c de Berg et al. (2008) , pág. 3.
- ^ Williams y Rossignac (2005) . Véase también Douglas Zare, respuesta a "el perímetro de un conjunto no convexo" , MathOverflow , 16 de mayo de 2014.
- ^ Oberman (2007) .
- ^ Knuth (1992) .
- ↑ a b Rockafellar (1970) , p. 12; Lay (1982) , pág. 17.
- ^ de Berg y col. (2008) , pág. 6. La idea de dividir el casco en dos cadenas proviene de una variante eficiente de la exploración de Graham de Andrew (1979) .
- ^ Sontag (1982) .
- ^ Rockafellar (1970) , p. 99.
- ↑ Steinitz (1914) ; Gustin (1947) ; Bárány, Katchalski y Pach (1982)
- ^ Grünbaum (2003) , p. dieciséis; Lay (1982) , pág. 21; Sakuma (1977) .
- ↑ Este ejemplo lo da Talman (1977) , Observación 2.6.
- ^ Whitley (1986) .
- ^ Kerin y Milman (1940) ; Lay (1982) , pág. 43.
- ^ Okon (2000) .
- ^ Kiselman (2002) .
- ^ Kashiwabara, Nakamura y Okamoto (2005) .
- ^ Kerin y Šmulian (1940) , Teorema 3, páginas 562–563; Schneider (1993) , Teorema 1.1.2 (páginas 2-3) y Capítulo 3.
- ^ de Berg y col. (2008) , pág. 254.
- ^ Grünbaum (2003) , p. 57.
- ^ de Berg y col. (2008) , pág. 256.
- ^ de Berg y col. (2008) , pág. 245.
- ^ Rappoport (1992) .
- ^ Demaine y col. (2008) .
- ^ Cranston, Hsu y marzo (1989) .
- ^ Sedykh (1981) .
- ^ Dirnböck y Stachel (1997) .
- ^ Seaton (2017) .
- ^ Rockafellar (1970) , p. 36.
- ^ Rockafellar (1970) , p. 149.
- ^ Avis, Bremner y Seidel (1997) .
- ^ de Berg y col. (2008) , pág. 13.
- ^ Chazelle (1993) ; de Berg y col. (2008) , pág. 256.
- ^ McCallum y Avis (1979) ; Graham y Yao (1983) ; Lee (1983) .
- ^ Chan (2012) .
- ^ Basch, Guibas y Hershberger (1999) .
- ^ Toussaint (1983) .
- ↑ a b c Westermann (1976) .
- ^ Laurentini (1994) .
- ↑ a b Edelsbrunner, Kirkpatrick y Seidel (1983) .
- ^ Toussaint (1986) .
- ^ Ottmann, Soisalon-Soininen y Wood (1984) .
- ^ Herrlich (1992) .
- ^ Rossi (1961) .
- ^ Marrón (1979) .
- ^ Chazelle (1985) .
- ^ Chang y Yap (1986) .
- ^ Artin (1967) ; Gel'fand, Kapranov y Zelevinsky (1994)
- ^ Prasolov (2004) .
- ^ Johnson (1976) .
- ^ Gardner (1984) .
- ^ Reay (1979) .
- ^ Epstein y Marden (1987) .
- ^ Semanas (1993) .
- ^ Rousseeuw, Ruts y Tukey (1999) .
- ^ Harris (1971) .
- ^ Pulleyblank (1983) ; véanse especialmente las observaciones que siguen al teorema 2.9.
- ^ Katoh (1992) .
- ^ Nicola (2000) . Véase en particular la Sección 16.9, No convexidad y equilibrio aproximado, págs. 209–210.
- ^ Chen y Wang (2003) .
- ^ Mason (1908) .
- ^ Kernohan, Gitzen y Millspaugh (2001) , p. 137-140; Nilsen, Pedersen y Linnell (2008)
- ^ Worton (1995) .
- ^ Getz y Wilmers (2004) .
- ^ Rieffel y Polak (2011) .
- ^ Kirkpatrick (2006) .
- ↑ Newton (1676) ; ver Auel (2019) , página 336, y Escobar & Kaveh (2020) .
- ^ Véase, por ejemplo, White (1923) , página 520.
- ^ Dines (1938) .
Referencias
- Andrew, AM (1979), "Otro algoritmo eficiente para cascos convexos en dos dimensiones", Information Processing Letters , 9 (5): 216-219, doi : 10.1016 / 0020-0190 (79) 90072-3
- Artin, Emil (1967), "2.5. Polígono de Newton" , Números algebraicos y funciones algebraicas , Gordon y Breach, págs. 37–43, MR 0237460
- Auel, Asher (2019), "Las matemáticas de Grace Murray Hopper" (PDF) , Notices of the American Mathematical Society , 66 (3): 330–340, MR 3889348
- Avis, David ; Bremner, David; Seidel, Raimund (1997), "¿Qué tan buenos son los algoritmos de casco convexo?", Geometría computacional , 7 (5-6): 265-301, doi : 10.1016 / S0925-7721 (96) 00023-5 , MR 1447243
- Bárány, Imre ; Katchalski, Meir; Pach, János (1982), "Teoremas cuantitativos de tipo Helly", Proceedings of the American Mathematical Society , 86 (1): 109-114, doi : 10.2307 / 2044407 , MR 0663877
- Basch, Julien; Guibas, Leonidas J .; Hershberger, John (1999), "Estructuras de datos para datos móviles", Journal of Algorithms , 31 (1): 1–28, CiteSeerX 10.1.1.134.6921 , doi : 10.1006 / jagm.1998.0988 , MR 1670903
- Birkhoff, Garrett (1935), "Integración de funciones con valores en un espacio de Banach", Transactions of the American Mathematical Society , 38 (2): 357–378, doi : 10.2307 / 1989687 , MR 1501815
- Brown, KQ (1979), "Diagramas de Voronoi de cascos convexos", Information Processing Letters , 9 (5): 223–228, doi : 10.1016 / 0020-0190 (79) 90074-7
- de Berg, M .; van Kreveld, M .; Overmars, Mark ; Schwarzkopf, O. (2008), Geometría computacional: Algoritmos y aplicaciones (3.a ed.), Springer
- Chan, Timothy M. (2012), "Tres problemas sobre cascos convexos dinámicos", International Journal of Computational Geometry and Applications , 22 (4): 341–364, doi : 10.1142 / S0218195912600096 , MR 2994585
- Chang, JS; Yap, C.-K. (1986), "Una solución polinomial para el problema del pelado de patatas", Geometría discreta y computacional , 1 (2): 155-182, doi : 10.1007 / BF02187692 , MR 0834056
- Chazelle, Bernard (1985), "Sobre las capas convexas de un conjunto plano", IEEE Transactions on Information Theory , 31 (4): 509–517, doi : 10.1109 / TIT.1985.1057060 , MR 0798557
- Chazelle, Bernard (1993), "Un algoritmo de casco convexo óptimo en cualquier dimensión fija" (PDF) , Geometría discreta y computacional , 10 (1): 377–409, CiteSeerX 10.1.1.113.8709 , doi : 10.1007 / BF02573985
- Chen, Qinyu; Wang, Guozhao (marzo de 2003), "A class of Bézier-like curves", Computer Aided Geometric Design , 20 (1): 29–39, doi : 10.1016 / s0167-8396 (03) 00003-7
- Cranston, M .; Hsu, P .; March, P. (1989), "Suavidad del casco convexo del movimiento browniano planar", Annals of Probability , 17 (1): 144-150, JSTOR 2244202 , MR 0972777
- Demaine, Erik D .; Gassend, Blaise; O'Rourke, Joseph ; Toussaint, Godfried T. (2008), "Todos los polígonos se voltean finitamente ... ¿verdad?", Encuestas sobre geometría discreta y computacional , Matemáticas contemporáneas, 453 , Providence, Rhode Island: American Mathematical Society, págs. 231-255, doi : 10.1090 / conm / 453/08801 , MR 2405683
- Dines, LL (1938), "Sobre la convexidad", American Mathematical Monthly , 45 (4): 199-209, doi : 10.2307 / 2302604 , JSTOR 2302604 , MR 1524247
- Dirnböck, Hans; Stachel, Hellmuth (1997), "El desarrollo del oloide" (PDF) , Journal for Geometry and Graphics , 1 (2): 105-118, MR 1622664
- Edelsbrunner, Herbert ; Kirkpatrick, David G .; Seidel, Raimund (1983), "On the shape of a set of points in the plane", IEEE Transactions on Information Theory , 29 (4): 551–559, doi : 10.1109 / TIT.1983.1056714
- Epstein, DBA ; Marden, A. (1987), "Cascos convexos en el espacio hiperbólico, un teorema de Sullivan y superficies plisadas medidas", en Epstein, DBA (ed.), Aspectos analíticos y geométricos del espacio hiperbólico (Coventry / Durham, 1984) , London Mathematical Society Lecture Note Series, 111 , Cambridge: Cambridge University Press, págs. 113–253, MR 0903852
- Escobar, Laura; Kaveh, Kiumars (septiembre de 2020), "Politopos convexos, geometría algebraica y combinatoria" (PDF) , Notices of the American Mathematical Society , 67 (8): 1116–1123
- Gardner, L. Terrell (1984), "Una prueba elemental del teorema de Russo-Dye", Actas de la American Mathematical Society , 90 (1): 171, doi : 10.2307 / 2044692 , MR 0722439
- Gel'fand, IM ; Kapranov, MM ; Zelevinsky, AV (1994), "6. Politopos de Newton y politopos de Chow", Discriminantes, resultantes y determinantes multidimensionales , Matemáticas: teoría y aplicaciones, Birkhäuser, págs. 193-213, doi : 10.1007 / 978-0-8176-4771 -1 , ISBN 0-8176-3660-9, MR 1264417
- Getz, Wayne M .; Wilmers, Christopher C. (2004), "Una construcción local de casco convexo del vecino más cercano de áreas de distribución y distribuciones de utilización" (PDF) , Ecografía , Wiley, 27 (4): 489–505, doi : 10.1111 / j.0906 -7590.2004.03835.x
- Graham, Ronald L .; Yao, F. Frances (1983), "Encontrar el casco convexo de un polígono simple", Journal of Algorithms , 4 (4): 324–331, doi : 10.1016 / 0196-6774 (83) 90013-5 , MR 0729228
- Grünbaum, Branko (2003), Politopos convexos , Textos de posgrado en matemáticas, 221 (2a ed.), Springer, ISBN 9780387004242
- Gustin, William (1947), "En el interior del casco convexo de un conjunto euclidiano", Boletín de la American Mathematical Society , 53 : 299–301, doi : 10.1090 / S0002-9904-1947-08787-5 , MR 0020800
- Harris, Bernard (1971), "Modelos matemáticos para la teoría de la decisión estadística" (PDF) , Optimización de métodos en estadística (Proc. Sympos., Ohio State Univ., Columbus, Ohio, 1971) , págs. 369–389, MR 0356305
- Herrlich, Horst (1992), "Cascos hiperconvexos de espacios métricos", Actas del Simposio sobre topología general y aplicaciones (Oxford, 1989), Topología y sus aplicaciones , 44 (1-3): 181-187, doi : 10.1016 / 0166-8641 (92) 90092-E , MR 1173256
- Johnson, Charles R. (1976), "Normalidad y rango numérico", Álgebra lineal y sus aplicaciones , 15 (1): 89–94, doi : 10.1016 / 0024-3795 (76) 90080-x , MR 0460358
- Kashiwabara, Kenji; Nakamura, Masataka; Okamoto, Yoshio (2005), "El teorema de representación afín para geometrías convexas abstractas", Geometría computacional , 30 (2): 129-144, CiteSeerX 10.1.1.14.4965 , doi : 10.1016 / j.comgeo.2004.05.001 , MR 2107032
- Katoh, Naoki (1992), "Problemas de optimización de red de Bicriteria", IEICE Trans. Fundamentos de electrónica, comunicaciones y ciencias de la computación , E75-A: 321–329
- Kernohan, Brian J .; Gitzen, Robert A .; Millspaugh, Joshua J. (2001), "Análisis del uso y los movimientos del espacio de los animales", en Millspaugh, Joshua; Marzluff, John M. (eds.), Seguimiento de radio y poblaciones animales , Academic Press, ISBN 9780080540221
- Kirkpatrick, KA (2006), "El teorema de Schrödinger-HJW", Fundamentos de las letras de la física , 19 (1): 95-102, arXiv : quant-ph / 0305068 , doi : 10.1007 / s10702-006-1852-1
- Kiselman, Christer O. (2002), "Un semigrupo de operadores en la teoría de la convexidad", Transactions of the American Mathematical Society , 354 (5): 2035-2053, doi : 10.1090 / S0002-9947-02-02915-X , MR 1881029
- Knuth, Donald E. (1992), Axioms and Hulls , Lecture Notes in Computer Science, 606 , Heidelberg: Springer-Verlag, doi : 10.1007 / 3-540-55611-7 , ISBN 3-540-55611-7, MR 1226891
- Kőnig, Dénes (diciembre de 1922), "Über konvexe Körper", Mathematische Zeitschrift , 14 (1): 208–210, doi : 10.1007 / bf01215899; véase también la reseña de Hans Rademacher (1922), JFM 48.0835.01
- Kerin, Mark ; Milman, David (1940), "En puntos extremos de conjuntos convexos regulares" , Studia Mathematica , 9 : 133-138
- Kerin, M .; Šmulian, V. (1940), "En conjuntos regularmente convexos en el espacio conjugado a un espacio de Banach", Annals of Mathematics , Second Series, 41 : 556–583, doi : 10.2307 / 1968735 , hdl : 10338.dmlcz / 100106 , JSTOR 1968735 , MR 0002009
- Laurentini, A. (1994), "El concepto de casco visual para la comprensión de imágenes basadas en siluetas", IEEE Transactions on Pattern Analysis and Machine Intelligence , 16 (2): 150-162, doi : 10.1109 / 34.273735
- Lay, Steven R. (1982), Conjuntos convexos y sus aplicaciones , John Wiley & Sons, ISBN 0-471-09584-2, MR 0655598
- Lee, DT (1983), "Al encontrar el casco convexo de un polígono simple", International Journal of Computer and Information Sciences , 12 (2): 87–98, doi : 10.1007 / BF00993195 , MR 0724699
- Mason, Herbert B. (1908), Encyclopaedia of Ships and Shipping , pág. 698
- McCallum, Duncan; Avis, David (1979), "Un algoritmo lineal para encontrar el casco convexo de un polígono simple", Information Processing Letters , 9 (5): 201-206, doi : 10.1016 / 0020-0190 (79) 90069-3 , MR 0552534
- Newton, Isaac (24 de octubre de 1676), "Carta a Henry Oldenburg" , The Newton Project , Universidad de Oxford
- Nicola, Piercarlo (2000), "Equilibrio competitivo general", Mainstream Mathematical Economics in the 20th Century , Springer, pp. 197-215, doi : 10.1007 / 978-3-662-04238-0_16
- Nilsen, Erlend B .; Pedersen, Simen; Linnell, John DC (2008), "¿Se pueden utilizar los rangos de hogar de polígonos convexos mínimos para sacar conclusiones biológicamente significativas?", Ecological Research , 23 (3): 635–639, doi : 10.1007 / s11284-007-0421-9
- Oberman, Adam M. (2007), "La envolvente convexa es la solución de un problema de obstáculos no lineales", Proceedings of the American Mathematical Society , 135 (6): 1689-1694, doi : 10.1090 / S0002-9939-07-08887 -9 , MR 2286077
- Okon, T. (2000), "Teoría de Choquet en espacios métricos", Zeitschrift für Analysis und ihre Anwendungen , 19 (2): 303–314, doi : 10.4171 / ZAA / 952 , MR 1768994
- Ottmann, T .; Soisalon-Soininen, E .; Wood, Derick (1984), "Sobre la definición y el cálculo de cascos convexos rectilíneos", Ciencias de la información , 33 (3): 157-171, doi : 10.1016 / 0020-0255 (84) 90025-2
- Prasolov, Victor V. (2004), "1.2.1 El teorema de Gauss-Lucas" , Polinomios , algoritmos y computación en matemáticas, 11 , Springer, pp. 12-13, doi : 10.1007 / 978-3-642-03980- 5 , ISBN 3-540-40714-6, Señor 2082772
- Pulleyblank, WR (1983), "Combinatoria poliédrica", en Bachem, Achim; Korte, Bernhard; Grötschel, Martin (eds.), Programación matemática: el estado del arte (XI Simposio Internacional de Programación Matemática, Bonn 1982) , Springer, págs. 312-345, doi : 10.1007 / 978-3-642-68874-4_13
- Rappoport, Ari (1992), "Un algoritmo adaptativo eficiente para construir el árbol de diferencias convexas de un polígono simple", Computer Graphics Forum , 11 (4): 235-240, doi : 10.1111 / 1467-8659.1140235
- Reay, John R. (1979), "Varias generalizaciones del teorema de Tverberg", Israel Journal of Mathematics , 34 (3): 238–244 (1980), doi : 10.1007 / BF02760885 , MR 0570883
- Rieffel, Eleanor G .; Polak, Wolfgang H. (2011), Computación cuántica: una suave introducción , MIT Press, págs. 215-216, ISBN 978-0-262-01506-6
- Rockafellar, R. Tyrrell (1970), Análisis convexo , Princeton Mathematical Series, 28 , Princeton, Nueva Jersey: Princeton University Press, MR 0274683
- Rossi, Hugo (1961), "Conjuntos holomórficamente convexos en varias variables complejas", Annals of Mathematics , Second Series, 74 : 470–493, doi : 10.2307 / 1970292 , JSTOR 1970292 , MR 0133479
- Rousseeuw, Peter J .; Ruts, Ida; Tukey, John W. (1999), "The bagplot: A bivariate boxplot", The American Statistician , 53 (4): 382–387, doi : 10.1080 / 00031305.1999.10474494
- Sakuma, Itsuo (1977), "Cerramiento de cascos convexos", Journal of Economic Theory , 14 (1): 223-227, doi : 10.1016 / 0022-0531 (77) 90095-3
- Schneider, Rolf (1993), Convex Bodies: The Brunn-Minkowski Theory , Encyclopedia of Mathematics and its Applications, 44 , Cambridge: Cambridge University Press, doi : 10.1017 / CBO9780511526282 , ISBN 0-521-35220-7, MR 1216521
- Seaton, Katherine A. (2017), "Esfericones y formas D: una conexión de ganchillo", Journal of Mathematics and the Arts , 11 (4): 187-202, arXiv : 1603.08409 , doi : 10.1080 / 17513472.2017.1318512 , MR 3765242
- Sedykh, VD (1981), "Estructura del casco convexo de una curva espacial", Trudy Seminara imeni IG Petrovskogo (6): 239-256, MR 0630708, traducido en Journal of Soviet Mathematics 33 (4): 1140-1153, 1986, doi : 10.1007 / BF01086114
- Sontag, Eduardo D. (1982), "Observaciones sobre álgebra lineal por partes" , Pacific Journal of Mathematics , 98 (1): 183-201, MR 0644949
- Steinitz, E. (1914), "Bedingt konvergente Reihen und konvexe Systeme. (Fortsetzung)", Journal für die Reine und Angewandte Mathematik , 144 : 1–40, doi : 10.1515 / crll.1914.144.1 , MR 1580890
- Talman, Louis A. (1977), "Puntos fijos para condensar multifunciones en espacios métricos con estructura convexa" , Kōdai Mathematical Seminar Reports , 29 (1–2): 62–70, MR 0463985
- Toussaint, Godfried (1983), "Resolver problemas geométricos con los calibradores giratorios", Actas de IEEE MELECON '83, Atenas , CiteSeerX 10.1.1.155.5671
- Toussaint, Godfried (1986), "Un algoritmo óptimo para calcular el casco convexo relativo de un conjunto de puntos en un polígono", Actas de EURASIP, Procesamiento de señales III: Teorías y aplicaciones, Parte 2 , Holanda Septentrional, págs. 853– 856
- Weeks, Jeffrey R. (1993), "Cascos convexos e isometrías de 3 colectores hiperbólicos cúspides", Topología y sus aplicaciones , 52 (2): 127-149, doi : 10.1016 / 0166-8641 (93) 90032-9 , Señor 1241189
- Westermann, LRJ (1976), "Sobre el operador del casco", Indagationes Mathematicae , 38 (2): 179–184, doi : 10.1016 / 1385-7258 (76) 90065-2 , MR 0404097
- White, F. Puryer (abril de 1923), "Matemáticas puras", Science Progress in the Twentieth Century , 17 (68): 517–526, JSTOR 43432008
- Whitley, Robert (1986), "El teorema de Kreĭn-Šmulian", Proceedings of the American Mathematical Society , 97 (2): 376–377, doi : 10.2307 / 2046536 , MR 0835903
- Williams, Jason; Rossignac, Jarek (2005), "Tensado: simplificación morfológica que limita la curvatura", en Kobbelt, Leif; Shapiro, Vadim (eds.), Actas del Décimo Simposio de ACM sobre Modelado Físico y Sólido 2005, Cambridge, Massachusetts, EE. UU., 13-15 de junio de 2005 , ACM, págs. 107–112, doi : 10.1145 / 1060244.1060257 , hdl : 1853/3736
- Worton, Bruce J. (1995), "Un estimador convexo basado en el casco del tamaño del rango de hogar", Biometrics , 51 (4): 1206-1215, doi : 10.2307 / 2533254 , JSTOR 2533254
enlaces externos
- "Casco convexo" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- Weisstein, Eric W. , "Convex Hull" , MathWorld
- "Convex Hull" por Eric W. Weisstein , Wolfram Demonstrations Project , 2007.