---

Mardi 30 Mai 2006, 14h Salle S16 (Passage Saumon, niveau -1)

• Orateur : Victor Chepoi , LIF, Marseille
• Titre : On covering planar graphs with a fixed number of balls
• Résumé:
  Dans cet exposé, nous montrons qu'il existe une constante $\rho$ telle que tout graphe planaire de diamètre $\le 2R$ peut être couvert avec au plus $\rho$ boules de rayon $R$. Ce résultat avait été conjecturé par C. Gavoille, D. Peleg, A. Raspaud et E. Sopena en 2001. La preuve utilise des concepts et des résultats de géométrie discrète. Travail en commun avec B. Estellon et Y. Vaxès.

---

Mardi 23 Mai 2006, 14h Salle S16 (Passage Saumon, niveau -1)

• Orateur : Hervé Brönnimann, CIS Dept, Polytechnic University, New York, USA
• Titre : Couverture optimale de clients par des disques pour differents couts ou bien "Comment arroser les carottes"
• Résumé:
  We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers and radii that cover a given set of demand points Y in R^2 at the smallest possible cost. We consider cost functions of the form: sum of f (r ), where r ranges over the disk radii and f(r) = r^alpha is the cost of transmission to radius r. Special cases arise for alpha = 1 (sum of radii) and alpha = 2 (total area); power consumption models in wireless network design often use an exponent alpha > 2. Different scenarios arise according to possible restrictions on the transmission centers , which may be constrained to belong to a given discrete set or to lie on a line, etc. We obtain several new results, including:
  
  (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y in R^2 ;
  
  (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y ;
  
  (c) a proof of NP-hardness for a discrete set of transmission points in R^2 and any fixed alpha > 1; and
  
  (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.
  
  This is joint work with Helmut Alt, Esther M. Arkin, Jeff Erickson, Sandor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, Sue Whitesides, and Kim Whittlesey.

---

Mardi 9 Mai 2006, 14h Salle S16 (Passage Saumon niveau -1)

• Orateur : Eméric Gioan, LIRMM (Montpellier)
• Titre : Matroides orientés et projections de graphes spatiaux
• Résumé:
  Les matroides orientés sont des structures combinatoires repérant notamment les positions relatives de points (ou d'hyperplans) dans l'espace réel, et en général les positions relatives de pseudosphères. En particulier, en rang 3, les matroôdes orientés sont équivalents aux arrangements de pseudodroites. Le théorème de Ringel indique que deux tels arrangements en position générale peuvent être liés par une suite de mutations de triangles. Ce résultat se généralise aux dessins du graphe complet, et cette généralisation s'applique à son tour aux projections (ou visualisations) du graphe spatial défini par un ensemble de points (en dimension 3) dont les positions sont codées par un matroide orienté (de rang 4).

---

Mardi 17 Janvier 2006, 14h Salle S16 (Passage Saumon, niveau -1)

• Orateur : Andreas Holmsen, Univ. Bergen, Norway
• Titre : Encoding of families of convex sets in the plane
• Résumé:
  We describe a combinatorial encoding of planar families of convex sets which generalizes the notion of allowable sequences which encode finite point sets in the plane. We also discuss some combinatorial problems concerning planar families of convex sets and how they translate into our combinatorial model.

---

Mardi 17 janvier 2006, 15h Salle S16 (Passage Saumon, niveau -1)

• Orateur : Luc Habert, Ecole normale supérieure
• Titre : Un théorème d'homotopie pour les arrangements de double pseudodroites
• Résumé:
  Une double pseudodroite est une courbe simple dans le ruban de Möbius homotope au double de son équateur et un arrangement de doubles pseudodroites est un ensemble fini de doubles pseudodroites tel que toute paire induit une décomposition cellulaire du ruban de Möbius combinatoirement équivalente à la décomposition induite par les courbes des tangentes aux bords de deux convexes bornés de dimension deux disjoints du plan affine.
  
  Nous montrons que deux arrangements de doubles pseudodroites de même taille sont homotopes et que tout arrangement de doubles pseudodroites est représentable par un ensemble de convexes deux-à-deux disjoints du plan affine équipé en guise de double tangentes d'un arrangement de pseudodroites.
  
  (Travail en collaboration avec Michel Pocchiola.)