Conjunto K (geometría)

Puntos separados de otros por una línea.

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

En geometría discreta , un conjunto de un punto finito establecido en el plano euclidiano es un subconjunto de elementos que pueden separarse estrictamente de los puntos restantes mediante una línea . De manera más general, en el espacio euclidiano de dimensiones superiores, un conjunto de puntos finitos es un subconjunto de elementos que pueden separarse de los puntos restantes mediante un hiperplano . En particular, cuando (dónde está el tamaño de ), la línea o hiperplano que separa un conjunto del resto es una línea que reduce a la mitad o un plano que reduce 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 una disposición de líneas . El nivel en una disposición de líneas en el plano es la curva que consta de los puntos que se encuentran en una de las líneas y tienen exactamente líneas debajo de ellas. Los geómetras discretos y computacionales también han estudiado niveles en disposiciones de tipos más generales de curvas y superficies. ^[1] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Límites combinatorios

Problema no resuelto en matemáticas :

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

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

Es importante en el análisis de algoritmos geométricos limitar el número de conjuntos de un conjunto de puntos planos, ^[2] o, de manera equivalente, el número de niveles de una disposición de líneas planas, 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 numérica cruzada 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 muestra 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 puntos en tres dimensiones que están en 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 acotar la complejidad de los diagramas de Voronoi de orden th. ^[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 en el que (reducir a la mitad las líneas), el número máximo de líneas combinatoriamente distintas que pasan por dos puntos de ese bisectriz de 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 el OEIS ).

También se han demostrado límites en el número de conjuntos, donde un conjunto es un conjunto para algunos . 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 plano que construye el nivel en orden de izquierda a derecha. Visto en términos de conjuntos de puntos, su algoritmo mantiene un casco convexo dinámico para los puntos a cada lado de una línea de separación, encuentra repetidamente una bitangente de estos dos cascos y mueve cada uno de los dos puntos de tangencia al casco opuesto. . Chan ^[12] analiza los resultados posteriores sobre este problema y muestra que se puede resolver 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 eficientemente 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 . Muestran que se puede encontrar una aproximación de este tipo, que consta de un número de segmentos de línea que depende únicamente de o no de o . ^[13] ${\displaystyle (k-\delta )}$ ${\displaystyle (k+\delta )}$ ${\displaystyle \delta }$ ${\displaystyle n/\delta }$ ${\displaystyle n}$ ${\displaystyle k}$

Generalizaciones matroides

El problema de nivel plano se puede generalizar a uno de optimización paramétrica en una matroide : se le da una matroide en la que cada elemento está ponderado por una función lineal de un parámetro , y se debe encontrar la base de peso mínimo de la matroide para cada valor posible. de . Si se grafican las funciones de peso como líneas en un plano, el nivel de disposición de estas líneas se grafica como una función del peso del elemento más grande en una base óptima en una matroide uniforme , y Dey demostró que su límite en la complejidad del nivel podría generalizarse 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 aplica para contar el número de diferentes árboles de expansión mínima 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 paramétrico de árbol de expansión mínimo ha sido estudiado por varios autores y puede usarse para resolver otros problemas de optimización de árbol de expansión 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 de conjuntos. ^[15] Para matroides más generales, el límite superior de Dey tiene un límite inferior coincidente. ^[dieciséis] ${\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 et al. 1973.
5. Dey 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. Epstein 1998.

Referencias

• Agarwal, PK (1990). "Disposiciones de partición 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 niveles en disposiciones de rectas, segmentos, planos y triángulos". Proc. 13º Simposio Anual sobre Geometría Computacional . págs. 30–38.
• Alón, N .; Győri, E. (1986). "El número de pequeños semiespacios de un conjunto finito de puntos en el plano". Revista de teoría combinatoria . Serie A. 41 : 154-157. doi : 10.1016/0097-3165(86)90122-6 .
• Chan, TM (1999). "Observaciones sobre algoritmos de nivel k en el avión". Archivado desde el original el 4 de noviembre de 2010.
• Chan, TM (2003). "Sobre niveles en disposiciones de curvas". Geometría discreta y computacional . 29 (3): 375–393. doi : 10.1007/s00454-002-2840-2 .
• Chan, TM (2005a). "Sobre niveles en disposiciones 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 niveles en disposiciones 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 del cuello de botella más corto en un árbol de expansión mínimo 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 el semiespacio: una aplicación algorítmica de k-conjuntos". Geometría discreta y computacional . 1 (1): 83–93. doi : 10.1007/BF02187685 . SEÑOR  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 .; Sí, CK (1987). "Sobre k -cascos y problemas relacionados". Revista SIAM de Computación . 16 (1): 61–77. doi :10.1137/0216005. SEÑOR  0873250.
• Dey, TK (1998). "Límites mejorados para conjuntos k planos y problemas relacionados". Geometría discreta y computacional . 19 (3): 373–382. doi : 10.1007/PL00009354 . SEÑOR  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 matroide paramétrica" ​​(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 para los árboles de expansión mínima paramétrica". Algorítmica . 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, Colorado, 1971) . Amsterdam: Holanda Septentrional. págs. 139-149. SEÑOR  0363986.
• Fernández-Baca, D.; Slutzki, G.; Eppstein, D. (1996). "Uso de la dispersión para problemas de árbol de expansión mínimo paramétrico". Revista Nórdica de Computación . 3 (4): 352–366.
• Gusfield, D. (1980). Análisis de sensibilidad para optimización combinatoria . Tecnología. Rep. UCB/ERL M80/22. Universidad de California, Berkeley.
• Hassin, R.; Tamir, A. (1989). "Maximizar clases de objetivos de dos parámetros 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 del árbol de expansión estocástico". Matemática Aplicada Discreta . 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 determinados problemas de optimización combinatoria paramétrica . Documento de trabajo 71. Inst. Economía. Res., Universidad de Kobe. de Comercio.
• Lee, Der-Tsai (1982). "En k -diagramas de Voronoi del vecino más cercano en el avión". Transacciones IEEE en computadoras . 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 . SEÑOR  1064574.
• Matoušek, J. (1991). "Niveles aproximados en disposiciones de línea". Revista SIAM de Computación . 20 (2): 222–227. doi :10.1137/0220013.
• Sharir, M .; Smorodinsky, S.; Tardós, 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 líneas y series de k, Jeff Erickson
• El Proyecto de Problemas Abiertos, Problema 7: conjuntos k