Simultaneous containment of polygons in a polygonal environment
F. Rebufat

     Dans  cet  article nous introduisons un cadre théorique pour
l'étude du placement de polygones. En nous aidant  de  ce  modèle
nous proposons une analyse de complexité pour le placement simul­
tané de plusieurs polygones en translation.  Nous  comparons  nos
résultats  à  ceux précédemment établis ( essentiellement ceux de
F. Avnaim), obtenant des bornes similaires (  parfois  meilleures
),  montrant  la complexité inhérante à ces algorithmes. La borne
de complexité exponentielle pour le placement de K polygones nous
amène à développer des méthodes décrivant l'espace des placements
possibles de manière partielle. Ces méthodes montrant des  bornes
de  complexité plus faibles peuvent être utilisées dans certaines
applications pour le calcul de trajectoires      The aim of  this
paper  is to introduce a theorical frame for polygons containment
problems. Using this frame we propose complexy analysis  for  si­
multaneous  containment  of  several  polygons in translation. We
compar our results  to  previous  works  (essentially  F.  Avnaim
works)  obtaining  similar  (sometimes better) bounds for general
configurations thatt show the inherant complexity of these  algo­
rithms.  The  exponential  complexity bound fot multiple polygons
containment lead us to develop methods that give partial  results
for free containment space. These methods having better complexi­
ty bounds could be effectively used to help in motion planing al­
gorithms.