Conjunto K (geometría)

Puntos separados de otros por una línea

Un conjunto de seis puntos (rojo), sus seis conjuntos 2 (los conjuntos de puntos contenidos en los óvalos azules) y líneas que separan cada conjunto de los puntos restantes (líneas discontinuas negras). ${\displaystyle k}$

En geometría discreta , un -conjunto de un conjunto finito de puntos en el plano euclidiano es un subconjunto de elementos de que se puede separar estrictamente de los puntos restantes por una línea . De manera más general, en el espacio euclidiano de dimensiones superiores, un -conjunto de un conjunto finito de puntos es un subconjunto de elementos que se puede separar de los puntos restantes por un hiperplano . En particular, cuando (donde es el tamaño de ), la línea o hiperplano que separa un -conjunto del resto de es una línea de reducción a la mitad o un plano de reducción a la mitad . ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle S}$

Los conjuntos de un conjunto de puntos en el plano están relacionados por dualidad proyectiva con los niveles en un arreglo de líneas . El nivel en un arreglo de líneas en el plano es la curva que consiste en los puntos que se encuentran en una de las líneas y tienen exactamente líneas debajo de ellos. Los geómetras discretos y computacionales también han estudiado los niveles en arreglos de tipos más generales de curvas y superficies. ^[1] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Límites combinatorios

Problema sin resolver en matemáticas :

¿Cuál es el mayor número posible de líneas de división a la mitad para un conjunto de puntos en el plano? ${\displaystyle n}$

(más problemas sin resolver en matemáticas)

En el análisis de algoritmos geométricos es importante acotar el número de conjuntos de un conjunto de puntos planar, ^[2] o equivalentemente el número de niveles de una disposición de líneas planar, un problema estudiado por primera vez por Lovász ^[3] y Erdős et al. ^[4] El límite superior más conocido para este problema es , como lo demostró Tamal Dey ^[5] utilizando la desigualdad de número de cruce de Ajtai, Chvátal , Newborn y Szemerédi . Sin embargo, el límite inferior más conocido está lejos del límite superior de Dey: es para alguna constante , como lo demostró Tóth. ^[6] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(nk^{1/3})}$ ${\textstyle \Omega (nc^{\sqrt {\log k}})}$ ${\displaystyle c}$

En tres dimensiones, el mejor límite superior conocido es , y el mejor límite inferior conocido es . ^[7] Para los puntos en tres dimensiones que están en la posición convexa , es decir, son los vértices de algún politopo convexo, el número de -conjuntos es , lo que se desprende de los argumentos utilizados para limitar la complejidad de los diagramas de Voronoi de orden . ^[8] ${\displaystyle O(nk^{3/2})}$ ${\textstyle \Omega (nkc^{\sqrt {\log k}})}$ ${\displaystyle k}$ ${\displaystyle \Theta {\bigl (}(n-k)k{\bigr )}}$ ${\displaystyle k}$

Para el caso cuando (reduciendo las líneas a la mitad), el número máximo de líneas combinatoriamente distintas a través de dos puntos de que bisecan los puntos restantes cuando es ${\displaystyle k=n/2}$ ${\displaystyle S}$ ${\displaystyle k=1,2,\dots }$

1,3,6,9,13,18,22... (secuencia A076523 en la OEIS ).

También se han demostrado límites en el número de conjuntos, donde un conjunto es un conjunto para algún . En dos dimensiones, el número máximo de conjuntos es exactamente , ^[9] mientras que en dimensiones el límite es . ^[10] ${\displaystyle \leq k}$ ${\displaystyle \leq k}$ ${\displaystyle j}$ ${\displaystyle j\leq k}$ ${\displaystyle \leq k}$ ${\displaystyle nk}$ ${\displaystyle d}$ ${\displaystyle O(n^{\lfloor d/2\rfloor }k^{\lceil d/2\rceil })}$

Algoritmos de construcción

Edelsbrunner y Welzl ^[11] estudiaron por primera vez el problema de construir todos los conjuntos de un conjunto de puntos de entrada, o dualmente, de construir el nivel de un arreglo. La versión de nivel de su algoritmo puede verse como un algoritmo de barrido de plano que construye el nivel en orden de izquierda a derecha. Visto en términos de conjuntos de conjuntos de puntos, su algoritmo mantiene una envoltura convexa dinámica para los puntos a cada lado de una línea de separación, encuentra repetidamente una bitangente de estas dos envolturas y mueve cada uno de los dos puntos de tangencia a la envoltura opuesta. Chan ^[12] examina resultados posteriores sobre este problema y demuestra que puede resolverse en un tiempo proporcional al límite de Dey sobre la complejidad del nivel. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(nk^{1/3})}$ ${\displaystyle k}$

Agarwal y Matoušek describen algoritmos para construir de manera eficiente un nivel aproximado; es decir, una curva que pasa entre el nivel y el nivel para algún pequeño parámetro de aproximación . Demuestran que se puede encontrar una aproximación de este tipo, que consiste en una cantidad de segmentos de línea que depende solo de y no de o . ^[13] ${\displaystyle (k-\delta )}$ ${\displaystyle (k+\delta )}$ ${\displaystyle \delta }$ ${\displaystyle n/\delta }$ ${\displaystyle n}$ ${\displaystyle k}$

Generalizaciones de matroides

El problema de nivel planar se puede generalizar a uno de optimización paramétrica en un matroide : se da un matroide en el que cada elemento está ponderado por una función lineal de un parámetro , y se debe encontrar la base de peso mínima del matroide para cada valor posible de . Si se grafican las funciones de peso como líneas en un plano, el nivel de la disposición de estas líneas se grafica como una función del peso del elemento más grande en una base óptima en un matroide uniforme , y Dey demostró que su límite en la complejidad del nivel se podía generalizar para contar el número de bases óptimas distintas de cualquier matroide con elementos y rango . ${\displaystyle k}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle k}$ ${\displaystyle \lambda }$ ${\displaystyle O(nk^{1/3})}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Por ejemplo, el mismo límite superior se cumple para contar la cantidad de árboles de expansión mínimos diferentes formados en un gráfico con aristas y vértices, cuando las aristas tienen pesos que varían linealmente con un parámetro . Este problema de árbol de expansión mínimo paramétrico ha sido estudiado por varios autores y se puede utilizar para resolver otros problemas de optimización de árboles de expansión de bicriterio. ^[14] ${\displaystyle O(nk^{1/3})}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \lambda }$

Sin embargo, el límite inferior más conocido para el problema del árbol de expansión mínimo paramétrico es , un límite más débil que el del problema del conjunto. ^[15] Para matroides más generales, el límite superior de Dey tiene un límite inferior coincidente. ^[16] ${\displaystyle \Omega (n\log k)}$ ${\displaystyle k}$ ${\displaystyle O(nk^{1/3})}$

Notas

1. Agarwal, Aronov y Sharir (1997); Chan (2003); Chan (2005a); Chan (2005b).
2. Chazelle y Preparata (1986); Cole, Sharir y Yap (1987); Edelsbrunner y Welzl (1986).
3. Lovász 1971.
4. Erdős y otros 1973.
5. Dios 1998.
6. Tóth 2001.
7. Sharir, Smorodinsky y Tardos 2001.
8. Lee (1982); Clarkson y Shor (1989).
9. Alon y Győri 1986.
10. Clarkson y Shor 1989.
11. Edelsbrunner y Welzl 1986.
12. Chan 1999.
13. Agarwal (1990); Matoušek (1990); Matoušek (1991).
14. Gusfield (1980); Ishii, Shiode y Nishida (1981); Katoh e Ibaraki (1983); Hassin y Tamir (1989); Fernández-Baca, Slutzki y Eppstein (1996); Chan (2005c).
15. Eppstein 2022.
16. Eppstein 1998.

Referencias

• Agarwal, PK (1990). "Disposiciones de particionamiento de líneas I: Un algoritmo determinista eficiente". Geometría discreta y computacional . 5 (1): 449–483. doi : 10.1007/BF02187805 .
• Agarwal, PK ; Aronov, B .; Sharir, M. (1997). "Sobre los niveles en disposiciones de líneas, segmentos, planos y triángulos". Proc. 13.º Simposio Anual sobre Geometría Computacional . págs. 30–38.
• Alon, N. ; Győri, E. (1986). "El número de semiespacios pequeños de un conjunto finito de puntos en el plano". Journal of Combinatorial Theory . Serie A. 41 : 154–157. doi : 10.1016/0097-3165(86)90122-6 .
• Chan, TM (1999). "Observaciones sobre algoritmos de nivel k en el plano". Archivado desde el original el 4 de noviembre de 2010.
• Chan, TM (2003). "Sobre niveles en arreglos de curvas". Geometría discreta y computacional . 29 (3): 375–393. doi : 10.1007/s00454-002-2840-2 .
• Chan, TM (2005a). "Sobre niveles en arreglos de curvas, II: una desigualdad simple y su consecuencia". Geometría discreta y computacional . 34 : 11–24. doi : 10.1007/s00454-005-1165-3 .
• Chan, TM (2005b). "Sobre los niveles en los arreglos de superficies en tres dimensiones". Actas del 16.º Simposio anual ACM-SIAM sobre algoritmos discretos . págs. 232–240.
• Chan, TM (2005c). "Encontrar el borde de cuello de botella más corto en un árbol de expansión mínima paramétrico". Actas del 16.º Simposio anual ACM-SIAM sobre algoritmos discretos . págs. 232–240.
• Chazelle, B. ; Preparata, FP (1986). "Búsqueda de rango en semiespacio: una aplicación algorítmica de conjuntos k". Geometría discreta y computacional . 1 (1): 83–93. doi : 10.1007/BF02187685 . MR  0824110.
• Clarkson, KL ; Shor, P. (1989). "Aplicaciones del muestreo aleatorio, II". Geometría discreta y computacional . 4 : 387–421. doi : 10.1007/BF02187740 .
• Cole, R.; Sharir, M .; Yap, CK (1987). "Sobre las k -envolturas y problemas relacionados". Revista SIAM de Computación . 16 (1): 61–77. doi :10.1137/0216005. MR  0873250.
• Dey, TK (1998). "Límites mejorados para conjuntos k planares y problemas relacionados". Geometría discreta y computacional . 19 (3): 373–382. doi : 10.1007/PL00009354 . MR  1608878.
• Edelsbrunner, H. ; Welzl, E. (1986). "Construcción de cinturones en disposiciones bidimensionales con aplicaciones". Revista SIAM de Computación . 15 (1): 271–284. doi :10.1137/0215019.
• Eppstein, D. (1998). "Límites inferiores geométricos para la optimización paramétrica de matroides" (PDF) . Geometría discreta y computacional . 20 (4): 463–476. doi : 10.1007/PL00009396 .
• Eppstein, David (agosto de 2022). "Un límite inferior más fuerte en árboles de expansión mínimos paramétricos". Algorithmica . arXiv : 2105.05371 . doi : 10.1007/s00453-022-01024-9 .
• Erdős, P. ; Lovász, L. ; Simmons, A.; Straus, EG (1973). "Gráficos de disección de conjuntos de puntos planos". Un estudio de la teoría combinatoria (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) . Ámsterdam: Holanda Septentrional. págs. 139–149. MR  0363986.
• Fernández-Baca, D.; Slutzki, G.; Eppstein, D. (1996). "Uso de esparsificación para problemas de árboles de expansión mínimos paramétricos". Nordic Journal of Computing . 3 (4): 352–366.
• Gusfield, D. (1980). Análisis de sensibilidad para optimización combinatoria . Tech. Rep. UCB/ERL M80/22. Universidad de California, Berkeley.
• Hassin, R.; Tamir, A. (1989). "Maximización de clases de objetivos biparamétricos sobre matroides". Matemáticas de la investigación de operaciones . 14 (2): 362–375. doi :10.1287/moor.14.2.362.
• Ishii, H.; Shiode, S.; Nishida, T. (1981). "Problema de árbol de expansión estocástico". Matemáticas Aplicadas Discretas . 3 (4): 263–273. doi : 10.1016/0166-218X(81)90004-4 .
• Katoh, N.; Ibaraki, T. (1983). Sobre el número total de pivotes necesarios para ciertos problemas de optimización combinatoria paramétrica . Documento de trabajo 71. Inst. Econ. Res., Universidad de Comercio de Kobe.
• Lee, Der-Tsai (1982). "Sobre los diagramas de Voronoi de k -vecinos más cercanos en el plano". IEEE Transactions on Computers . 31 (6): 478–487. doi :10.1109/TC.1982.1676031.
• Lovász, L. (1971). "Sobre el número de líneas reducidas a la mitad". Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica . 14 : 107-108.
• Matoušek, J. (1990). "Construcción de redes ε". Geometría discreta y computacional . 5 (5): 427–448. doi : 10.1007/BF02187804 . MR  1064574.
• Matoušek, J. (1991). "Niveles aproximados en disposiciones lineales". Revista SIAM de Computación . 20 (2): 222–227. doi :10.1137/0220013.
• Sharir, M. ; Smorodinsky, S.; Tardos, G. (2001). "Un límite mejorado para conjuntos k en tres dimensiones". Geometría discreta y computacional . 26 (2): 195–204. doi : 10.1007/s00454-001-0005-3 .
• Tóth, G. (2001). "Conjuntos de puntos con muchos conjuntos k". Geometría discreta y computacional . 26 (2): 187–194. doi : 10.1007/s004540010022 .

Enlaces externos

• Reducir a la mitad las líneas y los conjuntos k, Jeff Erickson
• Proyecto de problemas abiertos, problema 7: conjuntos k