| name | computational-geometry-topology |
| description | Compétence en recherche en géométrie computationnelle et topologie suivie sur arXiv sous cs.CG et math.AT. Couvre les algorithmes géométriques, les structures de données spatiales, la triangulation, les enveloppes convexes, la topologie algorithmique, la persistance homologique, l'analyse topologique des données (TDA) et la géométrie algorithmique pour ML. |
| category | research |
| arxiv_categories | ["cs.CG","math.AT","math.CO","cs.LG","stat.ML"] |
Compétence : Géométrie Computationnelle et Topologie
Présentation
Cette compétence couvre la recherche en géométrie computationnelle et topologie algorithmique : algorithmes géométriques, structures de données spatiales, triangulation, enveloppes convexes, homologie persistante, analyse topologique des données (TDA) et géométrie algorithmique pour l'apprentissage automatique. Suivi principal sur arXiv sous cs.CG (Computational Geometry) et math.AT (Algebraic Topology).
1. Algorithmes Géométriques
Enveloppes convexes
- Algorithmes 2D : Graham scan, Jarvis march, Chan
- Algorithmes 3D et haute dimension
- Enveloppes convexes dynamiques et semi-dynamiques
Triangulations
- Triangulation de Delaunay : existence, unicité, algorithmes (Bowyer-Watson, divide-and-conquer)
- Triangulation de Delaunay contrainte
- Triangulation de Delaunay en 3D (tétraédrisations)
- Triangulation de Delaunay pondérée (regular triangulations)
Diagrammes de Voronoi
- Diagramme de Voronoi standard et pondéré
- Diagramme de Voronoi additivement/multiplicativement pondéré
- Diagrammes d'ordre supérieur
- Applications : plus proche voisin, clustering spatial
Arrangements
- Arrangements de courbes et de surfaces
- Complexité combinatoire des arrangements
- Algorithmes pour les arrangements en 2D et 3D
- Applications : robotique, cartographie, géométrie algorithmique
2. Structures de Données Spatiales
kD-Trees
- Construction, équilibrage, k-d tree optimaux
- Recherche de plus proche voisin (approximative et exacte)
- Variantes : randomized kd-trees, priority search trees
R-Trees
- R-tree, R*-tree, R+-tree
- Requêtes spatiales : range queries, plus proche voisin, jointures spatiales
- Applications : bases de données spatiales, SIG
Quadtrees et Octrees
- Quadtrees (2D), octrees (3D), variants
- Applications : compression d'image, partitionnement spatial, simulations
- Mesh generation et raffinements adaptatifs
Range Searching
- Range trees, segment trees, interval trees
- Orthogonal range searching en haute dimension
- Structures dynamiques et semi-dynamiques
3. Topologie Algorithmique
Homologie persistante
- Persistance homologique : filtration, complexes de chaînes
- Algorithmes de calcul : matrice de réduction, algorithme standard
- Persistance en degré 0, 1, 2 (composantes, cycles, cavités)
- Variantes : zigzag persistence, multiparameter persistence
Complexes simpliciaux
- Complexe de Vietoris-Rips : construction, seuil, performance
- Complexe de Čech : relation avec Vietoris-Rips
- Complexe de Delaunay, alpha complexes
- Witness complexes, lazy witness complexes
Complexité computationnelle
- "Lower Bounds for Approximating the Vietoris-Rips Filtration" — bornes inférieures
- Approximations pour grandes données
- Algorithmes en streaming et dynamiques
4. Analyse Topologique des Données (TDA)
Code-barres (barcodes)
- Représentation graphique de la persistance
- Intervalles de persistance, naissance et mort des classes
- Stabilité des code-barres (bottleneck distance, Wasserstein distance)
Diagrammes de persistance
- Diagrammes comme signatures topologiques
- Distance entre diagrammes : bottleneck, Wasserstein, Kantorovich
- Intégration dans des espaces vectoriels (kernel methods)
Landscapes de persistance
- Persistence landscapes : transformation des diagrammes en fonctions
- Moyenne et variance dans l'espace des landscapes
- Régression et classification avec features topologiques
Signatures topologiques
- Persistence images
- Persistence curves
- Topological descriptors pour ML
5. TDA pour l'Apprentissage Automatique
Features topologiques
- Features topologiques pour nuages de points
- Persistent homology pour graphes et réseaux
- Topologie des variétés de données (manifold learning)
Applications ML
- Classification de formes et de textures
- Analyse de graphes (persistent homology on graphs)
- Détection d'anomalies topologiques
- Clustering avec persistance
TDA et Deep Learning
- Couches topologiques dans les réseaux de neurones
- Apprentissage de représentations topologiques
- Régularisation topologique pour l'entraînement
6. Géométrie Discrète et Combinatoire
Questions combinatoires
- Nombre de triangulations, arrangements
- Bornes supérieures et inférieures complexes
- Problèmes extrémaux en géométrie discrète
Géométrie algorithmique pour l'optimisation
- Optimisation sur polytopes
- Programmation linéaire et géométrie
- Minkowski sums et applications
Catégories arXiv
- cs.CG — Computational Geometry (géométrie algorithmique, structures, algorithmes)
- math.AT — Algebraic Topology (homologie, persistance, théorie)
- math.CO — Combinatorics (aspects combinatoires de la géométrie)
- cs.LG — Machine Learning (TDA pour ML, features topologiques)
- stat.ML — Statistics / Machine Learning (méthodes statistiques en TDA)
Articles Notables
- "Lower Bounds for Approximating the Vietoris-Rips Filtration" — Bornes inférieures pour l'approximation de la filtration de Vietoris-Rips
Stratégies de veille
- Surveiller les nouvelles soumissions sur cs.CG (quotidien)
- Suivre math.AT pour les avancées en topologie algébrique computationnelle
- Conférences clés : SoCG (Symposium on Computational Geometry), SGP, ATMCS (Algebraic Topology: Methods, Computation and Science)
- Journaux : Discrete & Computational Geometry, Journal of Computational Geometry, Topology and its Applications
- Mots-clés : Delaunay triangulation, Voronoi diagram, persistent homology, topological data analysis, Vietoris-Rips, convex hull, TDA
