38 artículos
Este artículo propone el uso de la homología persistente aplicada a un complejo de testigos para identificar brechas en la cobertura de centros de enfriamiento y evaluar el riesgo de mortalidad por calor, demostrando que esta perspectiva topológica complementa eficazmente los índices tradicionales de vulnerabilidad térmica.
Este artículo introduce un nuevo tipo de subgradiente basado en funciones de Busemann para espacios de Hadamard, permitiendo la generalización de métodos estocásticos e incrementales de subgradiente con garantías de complejidad para problemas de optimización convexa en espacios métricos no lineales como el espacio de árboles BHV.
El artículo demuestra que el diámetro del grafo dual de un arreglo de discos topológicos en el plano está acotado por una función de y (el número máximo de componentes conexas en la intersección de dos discos), estableciendo límites específicos como para dos discos y para el caso general, lo que implica que cualquier par de puntos puede conectarse cruzando un número acotado de fronteras de discos.
Este artículo utiliza la complejidad de precisión fina para analizar cómo la dimensionalidad, la simetría (dirigido vs. no dirigido) y la discretización afectan la complejidad temporal de calcular la distancia de Hausdorff bajo traslaciones, revelando asimetrías en los límites superiores e inferiores y reducciones a problemas como 3SUM y MaxConv.
Este artículo cierra la brecha entre los límites conocidos de la relación de estiramiento del grafo dirigido al demostrar que su valor exacto es 5, estableciendo así la primera cota ajustada para cualquier grafo dirigido.
El artículo demuestra que minimizar la longitud de la arista más larga en la incrustación geométrica simultánea de dos caminos en una cuadrícula entera es NP-duro, mientras que presenta un algoritmo de tiempo para minimizar el perímetro de la cuadrícula cuando un camino es -monótono y el otro es -monótono.
Este artículo caracteriza cuándo el desarrollo en banda de un prismatoide anidado resulta en un despliegue sin superposiciones, demostrando que el contraejemplo conocido es esencialmente el único caso posible y proporcionando herramientas que podrían ayudar a resolver el problema general de los prismatoides no anidados.
Los autores presentan un esquema de aproximación óptimo bajo Gap-ETH para el problema del viajante y el árbol de Steiner en espacios hiperbólicos de dimensión fija, logrando un tiempo de ejecución $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$ mediante una nueva descomposición jerárquica llamada "cuadrícula híbrida hiperbólica" y un análisis de cruces ponderados.
Este trabajo mejora el tiempo de ejecución de los algoritmos de aproximación para los problemas de -mediana y -medias en espacios euclídeos de baja dimensión a $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)$ y demuestra que este límite es casi óptimo bajo la Hipótesis del Tiempo Exponencial con Brecha para 3-SAT.
Este artículo establece relaciones entre invariantes de casi incrustaciones de grafos en el plano, conecta estos resultados con la homología del producto eliminado del grafo, construye ejemplos que realizan ciertos valores de dichos invariantes y presenta conceptos de topología algebraica y geométrica de manera accesible para no especialistas, incluyendo conjeturas y problemas abiertos.
Este trabajo propone un método sin parámetros para el coarsening de grafos espaciales que reduce su tamaño preservando sus características topológicas mediante el colapso de aristas cortas y una nueva filtración llamada "triangle-aware graph filtration".
Este trabajo presenta un método eficiente para la búsqueda de vecinos en nubes de puntos 3D que combina curvas de relleno espacial y octrees lineales, logrando una reducción de hasta 10 veces en el tiempo de búsqueda y una mejora significativa en el uso de la caché en comparación con soluciones existentes.
Este artículo presenta un marco geométrico y un flujo de trabajo de diseño para estructuras pop-up inspiradas en el origami y el kirigami, que permiten generar superficies con curvaturas variables mediante patrones de cortes y pliegues, con aplicaciones potenciales en reducción de arrastre, embalaje y fachadas arquitectónicas.
Este artículo investiga la no inyectividad de la Transformada de Homología Persistente Verbose (VPHT) en grafos verticales con vértices colineales, identificando propiedades necesarias y suficientes para su no reconstruibilidad.
Este artículo presenta la primera especificación formal y el análisis completo del árbol de Li-Chao, una estructura de datos ampliamente utilizada en programación competitiva para el mantenimiento dinámico de envolventes inferiores, incluyendo sus demostraciones de corrección, complejidad teórica y caracterización de rendimiento.
Este artículo determina que, para cualquier disposición de rectas en posición general, el número mínimo de piedras que Alice necesita para evitar que Bob gane en un juego de equilibrio geométrico es y que este valor es computable en tiempo polinómico.
Este artículo caracteriza la resolubilidad de los acertijos de coincidencia de permutaciones mediante la aciclicidad de un grafo de restricciones, proporciona una fórmula de longitud de gancho para contar las soluciones, ofrece un algoritmo lineal para reparar puzzles no resolubles y demuestra que la generalización con permutaciones arbitrarias es NP-completa.
Este artículo propone una formulación alternativa de la transformada de Hough que, al sustituir el esquema de votación discretizado por una función de puntuación continua, utiliza la homología persistente para identificar líneas en nubes de puntos y presenta un algoritmo eficiente para su cálculo.
Este artículo demuestra que el problema de extender un diseño de historia visual minimizando el número de cruces locales es W[1]-duro cuando se parametriza por el número de personajes insertados y activos, pero pertenece a las clases XP y FPT bajo diferentes combinaciones de parámetros.
Este artículo presenta algoritmos aleatorizados que mejoran los tiempos de ejecución existentes para calcular aproximaciones de la máxima clique en grafos de discos, logrando tiempos casi lineales para grafos de discos unitarios y esquemas de aproximación parametrizados para grafos con radios distintos.