37 artigos
Este artigo avalia a cobertura de centros de resfriamento em quatro cidades dos EUA utilizando a homologia persistente aplicada a um complexo de testemunha para identificar lacunas geográficas de risco térmico, comparando os resultados com um índice de vulnerabilidade ao calor tradicional para oferecer uma compreensão mais holística das áreas mais vulneráveis.
Este artigo introduz um novo tipo de subgradiente baseado em funções de Busemann para espaços de Hadamard, permitindo a generalização de métodos estocásticos e incrementais de subgradiente com limites de complexidade garantidos para problemas de otimização convexa, como o cálculo de médias e medianas em espaços de árvores BHV.
Este artigo estabelece limites superiores para o diâmetro do grafo dual de arranjos de discos topológicos no plano, demonstrando que ele é limitado por uma função de e (o número máximo de componentes conexos na interseção de dois discos), com limites específicos de para dois discos e para discos, resultados alcançados ao provar limites sobre o número de faces maximais e de máxima profundidade no arranjo.
Este artigo investiga a complexidade computacional de calcular a distância de Hausdorff sob a norma para conjuntos de pontos sob translações, revelando uma interação intricada entre dimensionalidade, simetria e discretização que resulta em limites de tempo assimétricos, separações condicionais entre variantes direcionadas e não direcionadas em dimensão 1, e barreiras distintas para provar limites inferiores em variantes discretas versus contínuas.
Este artigo estabelece que a razão de espalhamento do grafo direcionado é exatamente 5, fechando a lacuna entre os limites anteriores de 4 e 7 e fornecendo a primeira cota apertada provada para qualquer grafo .
Este artigo demonstra que minimizar o comprimento da aresta mais longa na incorporação geométrica simultânea de dois caminhos em uma grade inteira é NP-difícil, enquanto apresenta um algoritmo de tempo para minimizar o perímetro da grade quando um caminho é monotônico em e o outro em .
Este artigo caracteriza quando o desenrolamento em faixa de um prismatoide aninhado resulta em um desenrolamento sem sobreposições, demonstrando que o contraexemplo conhecido é essencialmente o único caso possível e fornecendo ferramentas que podem ajudar a resolver o problema geral do desenrolamento de prismatoides.
Os autores apresentam um esquema de aproximação Gap-ETH-ótimo para o Problema do Caixeiro Viajante e o Problema da Árvore de Steiner no espaço hiperbólico, alcançando um tempo de execução de $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$ por meio de uma nova decomposição hierárquica chamada "quadtree hiperbólico híbrido" e técnicas inovadoras de análise de cruzamento.
Este trabalho melhora o tempo de execução para o algoritmo de aproximação dos problemas de -média e -means em espaços euclidianos de baixa dimensão e estabelece um limite inferior quase correspondente, demonstrando que tal complexidade é essencial sob a Hipótese do Tempo Exponencial com Lacuna.
Este artigo estabelece relações entre invariantes de quase mergulhos de grafos no plano, conecta essas relações à homologia do produto deletado de um grafo, constrói exemplos que realizam certos valores desses invariantes e apresenta conceitos de topologia algébrica e geométrica de forma acessível a não especialistas, incluindo conjecturas e problemas em aberto.
Este trabalho propõe uma abordagem de coarsening para grafos espaciais que reduz o número de nós preservando as características topológicas essenciais através do colapso de arestas curtas, utilizando uma nova filtração "triangle-aware" para gerar diagramas de persistência adaptados, resultando em um método sem parâmetros, equivariante a transformações geométricas e eficaz na redução de tamanho dos grafos.
Este trabalho apresenta um método eficiente para busca de vizinhança em nuvens de pontos 3D que combina curvas de preenchimento espacial (Morton e Hilbert) com uma implementação linear de Octree, resultando em reduções significativas de falhas de cache e tempos de execução, superando em até 10 vezes soluções existentes e demonstrando alta escalabilidade paralela.
Este artigo explora a geometria das estruturas pop-up, combinando origami e kirigami para desenvolver um pipeline de projeto que permite criar superfícies com curvatura variável e transições de negativa para positiva, com aplicações em redução de arrasto, embalagens e fachadas arquitetônicas.
Este artigo investiga as condições de não reconstrutibilidade da Transformada de Homologia Persistente Verbose (VPHT) em grafos cujos vértices são colineares, identificando propriedades necessárias e suficientes para casos de degenerescência onde a transformada deixa de ser injetiva.
Este artigo apresenta a primeira especificação formal e análise completa da Árvore Li-Chao, uma estrutura de dados amplamente utilizada na programação competitiva para manutenção dinâmica de envoltórias inferiores, incluindo provas de correção, análise de complexidade e caracterizações de desempenho.
O artigo determina que, para qualquer arranjo de linhas em posição geral, o número mínimo de pedras necessário para que Alice garanta a vitória no jogo de equilíbrio geométrico é e pode ser calculado em tempo polinomial.
Este artigo caracteriza a solvabilidade de um novo tipo de quebra-cabeça de ordenação em grades, fornecendo uma fórmula para contar soluções válidas, um algoritmo linear para corrigir configurações insolúveis e demonstrando que a generalização do problema para permutações arbitrárias é NP-completa.
Este artigo propõe uma reformulação topologicamente estável da Transformada de Hough para detecção de linhas em nuvens de pontos, substituindo o esquema de votação discretizado por uma função de pontuação contínua cujas características persistentes, identificadas via homologia persistente, geram um conjunto de linhas candidatas calculadas eficientemente por um novo algoritmo.
Este artigo investiga a complexidade computacional do problema de estender layouts de histórias com personagens fixos ao inserir novos participantes, minimizando o número local de cruzamentos, e demonstra que o problema é W[1]-duro quando parametrizado pelo número de inserções e personagens ativos, pertence à classe XP em relação ao número de personagens ativos e é FPT quando parametrizado pela soma dos personagens ativos e do número local de cruzamentos.
Este artigo apresenta algoritmos aleatorizados de tempo quase linear que fornecem aproximações para o problema do clique máximo em grafos de discos, oferecendo uma solução eficiente para grafos de discos unitários e um esquema de aproximação parametrizado para grafos com raios distintos.