37 articles
Cet article propose une approche novatrice utilisant l'homologie persistante appliquée à un complexe témoin filtré pour identifier les lacunes dans la couverture des centres de rafraîchissement lors des vagues de chaleur, offrant ainsi une perspective complémentaire aux indices de vulnérabilité thermique traditionnels.
Cet article introduit un nouveau type de sous-gradient basé sur les fonctions de Busemann pour les espaces de Hadamard, permettant d'étendre les méthodes de sous-gradient stochastiques et incrémentales avec des garanties de complexité à des problèmes d'optimisation non linéaires tels que le calcul de médianes dans l'espace des arbres BHV.
Cet article établit des bornes sur le diamètre du graphe dual d'un arrangement de disques topologiques en fonction du nombre maximal de composantes connexes de leurs intersections, démontrant notamment que ce diamètre est au plus pour deux disques et dans le cas général.
Cet article établit une analyse de complexité fine des distances de Hausdorff sous translation en démontrant des bornes conditionnelles asymétriques selon la dimension, la symétrie et la discrétion des ensembles de points, révélant ainsi des séparations algorithmiques fondamentales entre les variantes continues et discrètes.
Cet article établit que le rapport d'étirement du graphe dirigé est exactement de 5, comblant ainsi la lacune entre les bornes précédentes de 4 et 7 et fournissant la première borne serrée prouvée pour un graphe dirigé.
Cet article démontre que la minimisation de la longueur de l'arête la plus longue dans l'insertion simultanée géométrique de deux chemins sur une grille entière est NP-difficile, tout en proposant un algorithme de complexité pour minimiser le périmètre de la grille lorsque l'un des chemins est monotone en et l'autre en .
Cet article caractérise les conditions sous lesquelles le dépliement en bande d'un prismatoïde emboîté est non chevauchant, démontrant que le contre-exemple connu est essentiellement le seul cas d'échec possible.
Cet article présente un schéma d'approximation Gap-ETH-optimal pour les problèmes du voyageur de commerce et de l'arbre de Steiner dans les espaces hyperboliques, reposant sur une nouvelle décomposition hiérarchique appelée « quadtree hyperbolique hybride » et une analyse de traversée pondérée.
Ce papier améliore le temps d'exécution des algorithmes d'approximation pour les problèmes de -médiane et -means en espaces euclidiens de faible dimension et établit une borne inférieure presque correspondante sous l'hypothèse du temps exponentiel.
Cet article établit des relations entre les invariants des presque-embeddings de graphes dans le plan, les relie à l'homologie du produit supprimé, construit des exemples réalisant certaines valeurs de ces invariants et présente des concepts de topologie algébrique et géométrique de manière accessible aux non-spécialistes tout en abordant des problèmes ouverts de recherche.
Cet article propose une méthode sans paramètre pour la coarsening de graphes spatiaux qui réduit leur taille en repliant les arêtes courtes tout en préservant leurs caractéristiques topologiques grâce à une nouvelle filtration adaptée aux diagrammes de persistance.
Cet article présente une méthode efficace pour la recherche de voisins dans les nuages de points 3D, combinant le réordonnancement spatial par courbes de Peano (Morton et Hilbert) et une implémentation d'octree linéaire, ce qui permet de réduire les défauts de cache et d'accélérer les temps de recherche jusqu'à 10 fois par rapport aux solutions existantes.
Cet article propose une description géométrique et une méthode de conception pour les structures popup inspirées de l'origami et du kirigami, permettant de générer des formes spécifiques et de faire varier la courbure de surface pour des applications en aérodynamique, en emballage et en architecture.
Cet article examine les cas où la transformée d'homologie persistante verbale (VPHT) n'est pas injective pour les graphes dont les sommets sont collinéaires, en identifiant des propriétés nécessaires et suffisantes pour leur non-reconstructibilité.
Cet article présente la première spécification formelle et l'analyse complète de l'arbre de Li-Chao, une structure de données largement utilisée en programmation compétitive pour la maintenance dynamique d'enveloppes inférieures, en y ajoutant des preuves de correction, une analyse de complexité et des caractérisations de performances empiriques.
Cet article détermine le nombre minimal de cailloux nécessaire pour qu'Alice puisse gagner un jeu d'équilibrage géométrique sur un arrangement de droites, prouvant que cette valeur est de l'ordre de et calculable en temps polynomial.
Cet article caractérise la résolubilité et le nombre de solutions des puzzles de correspondance de permutations sur grille, fournit un algorithme linéaire pour corriger les instances non résolubles, et démontre que la généralisation du problème à des permutations arbitraires est NP-complète.
Cet article propose une reformulation de la transformée de Hough pour la détection de lignes dans des nuages de points, en remplaçant le schéma de vote discret par une fonction de score continue dont les caractéristiques persistantes, calculées via l'homologie persistante, identifient les lignes candidates.
Cet article étudie la complexité algorithmique de l'extension de scénarios narratifs en insérant des personnages manquants tout en minimisant le nombre de croisements locaux, démontrant que le problème est W[1]-difficile, mais appartient à XP et FPT sous certaines paramétrisations.
Cet article présente des algorithmes randomisés permettant d'obtenir des approximations du problème du maximum de clique en temps quasi-linéaire pour les graphes de disques unitaires et en temps paramétré pour les graphes de disques à rayons distincts.