Simultaneous containment of polygons in a polygonal environment

F. Rebufat

IBP-Litp 1994/64: Rapport de Recherche Litp / Litp research reports
9 pages - Octobre/October 1994 - Document en anglais.

Titre / Title: Simultaneous containment of polygons in a polygonal environment

Résumé : 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 simultané 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

Abstract : The aim of this paper is to introduce a theorical frame for polygons containment problems. Using this frame we propose complexy analysis for simultaneous 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 algorithms. 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 complexity bounds could be effectively used to help in motion planing algorithms.

Publications internes Litp 1994 / Litp research reports 1994