Idees discutées avec X. Goaoc à Arcachon en avril

Le cours sera centré autour de LP et IP et de ses généralisations (en
particulier [DDGG09]).

Côté exercices

* Carathéodory effectif avec un LP

* Générer de petits programmes
   - graphes
   - optimisation de distances L1

* Problème de prédicats et de flottants / arithémtique d'intervalle

* Manipulation de polytopes
  (complexité des faces lorsqu'on prend des points sur la courbe des moments)

* il existe des exemples de problèmes IP qui sont en fait des LP
  (poids positifs sur les graphes tel que somme dans les cliques <= 1?)

* étant donné un nuage de point dans R^2 (ou petite dimension)
  trouver le plus petit cercle circonscrit contenant tous
  les points.
    Deux opérations:
     1) test de violation (on ajoute un point en dehors)
     2) résolution du problème sur 4 points (ou plus généralement taille constante)
  (analyse de complexité identique à Delaunay)
  cas des ellipses?
  faire pareil pour le plus grand disque contenu dans un polygone convexe
  idem intersection de disques

* calculer des nombres de Ramsey


[DDGG09]
Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc
"Helly-Type Theorems for Approximate Covering"
Discrete & Computational Geometry, October 2009, Volume 42, Issue 3, pp 379–398