Reconnaissance des plans discrets : simplification polygonale
Institution:
Clermont-Ferrand 1Disciplines:
Directors:
Abstract EN:
We study digital lines and planes recognition. Our method is based on a well-known linear programming method, namely Megiddo algorithm, wich is linear in the number of constraints. A new variant is given in order to preserve a linear complexity for the incremental algorithm. This rather intricate method having never been programmed, we propose the first simplified and proved implementation. Various recognition techniques are studied and we then develop efficient randomized algorithms. Megiddo algorithm requiring median computations, we compare the different approaches in a theoretical and experimental way. We finally create a more efficient algorithm compared with current methods. We conclude this work by providing an application of our results to the construction of the first subquadratic algorithm for polygonal simplification.
Abstract FR:
Nous étudions le problème de la reconnaissance des droites et des plans discrets. Notre méthode est fondée sur le célèbre algorithme de programmation linéaire de N. Megiddo, linéaire suivant le nombre de contraintes. Nous décrivons une variante originale permettant de maintenir une complexité linéaire dans le cas incrémental. Cette méthode complexe n'ayant jamais été programmée, nous proposons la première implémentation simplifiée et certifiée de cette technique. Les divers algorithmes de reconnaissance sont étudiés et nous envisageons ensuite des méthodes probabilistes plus efficaces en moyenne. L'algorithme de Megiddo requérant des calculs de valeurs médianes, nous comparons les différentes approches de manière théorique et expérimentale. Finalement nous construisons un algorithme plus efficace en moyenne que les méthodes actuelles. Nous concluons ce travail par une application de nos résultats permettant de créer le premier algorithme sous-quadratique de simplification polygonale.