. En-effet and . Dans-le, nous commencons par construire deux carrés de côté 4. Ensuite, dans le rectangle restant de dimensions 4 × 3, nous construisons un carré de côté 3. Enfin, dans le rectangle de dimensions 3 × 1, nous insérons trois carrés de côté 1, Cettedernì ere longueur correspond bien au pgcdàpgcdà calculer. Un vecteuràvecteurà coordonnéesentì eres dans le plan euclidien u = (u 1 , u 2 ) est irréductible si le pgcd de ses coordonnées u 1 et u 2 estégaìestégaì a 1

. La-méthode-de, plans discrets na¨?fsna¨?fs en unprobì eme de réalisabilité sur une fonction convexe bi-dimensionelle dite fonctionépaisseurfonctionépaisseur. Par conséquent, ces méthodes ne prennent en compte que deux paramètres et nous pouvons utiliser des techniques de géométrie discrète planaire afin de déterminer si l'espace des solutions 2D est vide ou pas. Pour résoudre leprobì eme de réalisabilité, notre approche actuelle utilise une propriété du centre de gravité tandis que la méthode de 2006 combine l'oracle de Megiddo et une recherche dichotomique mono-dimensionnelle. Ce principal changement améliore la complexité en temps de la méthode et diminue considérablement son nombre d'itérations, Notre algorithme peutégalementêtrepeutégalementpeutégalementêtre conçu de façon incrémentale. Dans la section 4.2, nous montrons comment leprobì eme de reconnaissance de plans discrets peutêtrepeutêtre transformé en unprobì eme de réalisabilité sur une fonction convexe bi- Chapitre 5, 2006.

C. Efficace-d-'´-epaisseur-dans-un-réseau, est donnée, dans chaque cône, pour les plus courts vecteurs du cône par rapportàrapportà la norme duale Ces plus courts vecteurs sont situés aux sommets de la voile de Klein associée au cône (voir [KS96] et la section 1.2.2) Notons que, pour avoir la possibilité de déterminer tous les vecteurs solutions, nous devons garder les répétitions dans l'enveloppe convexe. Pour calculer la voile de Klein dans chaque cône, nous pouvons adapter l'algorithme de Harvey [Har99] qui s'exécute en O(log s) opérations arithmétiques Afin de borner la complexité de la recherche, nous pouvons nous appuyer sur le théorème général de Cook et al. (voir [CHKM92]) qui indique qu'en dimension d le nombre de sommets de la voile de Klein est borné par O((log s) d?1 ) Ce dernier résultat a ´ egalementétéegalementété montré par Harvey

. [. Bibliographie, V. Alessandri, and . Berthé, Three distance theorems and combinatorics on words, pp.103-132, 1998.

]. A. And79 and . Andrew, Another efficient algorithm for convex hulls in two dimensions, Inf. Process. Lett, vol.9, issue.5, pp.216-219, 1979.

]. V. Arn98 and . Arnold, Higher dimensional continued fractions. Regular and chaotic dynamics, pp.10-17, 1998.

]. A. Bar02 and . Barvinok, A Course in Convexity, Graduates Studies in Mathematics. Amer. Math. Soc, vol.54, 2002.

D. [. Brimkov, R. Coeurjolly, and . Klette, Digital planarity???A review, Discrete Applied Mathematics, vol.155, issue.4, pp.468-495, 2007.
DOI : 10.1016/j.dam.2006.08.004
URL : https://hal.archives-ouvertes.fr/hal-00185059

S. [. Brimkov and . Dantchev, Digital hyperplane recognition in arbitrary fixed dimension within an algebraic computation model, Image and Vision Computing, vol.25, issue.10, pp.1631-1643, 2007.
DOI : 10.1016/j.imavis.2006.06.013

J. E. Boyce, D. P. Dobkin, R. L. Drysdale, and L. J. Guibas, Finding extremal polygons, STOC, pp.282-289, 1982.

D. [. Barber, H. Dobkin, and . Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software, vol.22, issue.4, pp.469-483, 1996.
DOI : 10.1145/235815.235821

J. [. Balza-gomez, D. Moreau, and . Michelucci, Convex Hull of Grid Points below a Line or a Convex Curve, DGCI, pp.361-374, 1999.
DOI : 10.1007/3-540-49126-0_28

L. [. Berthé and . Imbert, Diophantine approximation, ostrowski numeration and the double-base number system, Discrete Mathematics and Theoretical Computer Science Proceedings, vol.11, issue.1, pp.153-172, 2009.

]. A. Bre81 and . Brentjes, Multi-dimensional continued fraction algorithms, Mathematical Centre Tracks. Matematisch Centrum Amsterdam, vol.145, 1981.

]. J. Bur02 and . Burguet, Surface discrètes multi-´ echelle, squelettisation, polyédrisation et opérations ensemblistes sur les polyèdres, Thèse d'´ etat, 2002.

]. L. Buz02 and . Buzer, Reconnaissances des plans discrets -Simplication polygonale

]. L. Buz03 and . Buzer, A linear incremental algorithm for naive and standard digital lines and planes recognition, Graphical Models, vol.65, issue.1-3, pp.61-76, 2003.

]. L. Buz06 and . Buzer, A composite and quasi linear time method for digital plane recognition, DGCI, pp.331-342, 2006.

]. A. Byk78 and . Bykat, Convex hull for a finite set of points in two dimensions, IPL, vol.7, pp.296-298, 1978.

E. Charrier and L. Buzer, An Efficient and Quasi Linear Worst-Case Time Algorithm for Digital Plane Recognition, DGCI, pp.346-357, 2008.
DOI : 10.1007/978-3-540-79126-3_31
URL : https://hal.archives-ouvertes.fr/hal-00622023

]. E. Cb08b, L. Charrier, and . Buzer, Matching a straight line in a two-dimensional integer domain, EuroCG, Collection of abstracts, pp.173-176, 2008.

]. E. Cb08c, L. Charrier, and . Buzer, Reducing the coefficients of a two-dimensional integer linear constraint, IWCIA, pp.205-216, 2008.

L. [. Charrier and . Buzer, Approximating a real number by a rational number with a limited denominator: A geometric approach, Discrete Applied Mathematics, vol.157, issue.16, 2009.
DOI : 10.1016/j.dam.2009.03.005
URL : https://hal.archives-ouvertes.fr/hal-00622456

L. [. Charrier, F. Buzer, and . Feschet, Efficient Lattice Width Computation in Arbitrary Dimension, DGCI, pp.46-56, 2009.
DOI : 10.2307/1911124
URL : https://hal.archives-ouvertes.fr/hal-00827176

B. Chazelle, An optimal convex hull algorithm in any fixed dimension, Discrete & Computational Geometry, vol.16, issue.4, pp.377-409, 1993.
DOI : 10.1007/BF02573985

]. T. Cha96 and . Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, GEOMETRY : Discrete & Computational Geometry, vol.16, pp.361-368, 1996.

M. [. Cook, R. Hartman, C. Kannan, and . Mcdiarmid, On integer points in polyhedra, Combinatorica, vol.10, issue.No. 6, pp.27-37, 1992.
DOI : 10.1007/BF01191202

]. G. Chr89 and . Chrystal, Algebra : An elementary text-book Prt II, 1889.

S. [. Chand and . Kapur, An Algorithm for Convex Polytopes, Journal of the ACM, vol.17, issue.1, pp.78-86, 1970.
DOI : 10.1145/321556.321564

]. D. Coe02 and . Coeurjolly, Algorithmique et géométrie discrète pour la caractérisation des courbes et des surfaces, Thèse d'´ etat, 2002.

P. [. Clarkson and . Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, vol.1, issue.5, pp.387-421, 1989.
DOI : 10.1007/BF02187740

]. D. Csd-+-03, I. Coeurjolly, F. Sivignon, F. Dupont, J. Feschet et al., Digital plane preimage structure, Electronic Notes in Discrete Mathematics, vol.12, pp.220-231, 2003.

E. [. Dexet and . Andres, A generalized preimage for the digital analytical hyperplane recognition, Discrete Applied Mathematics, vol.157, issue.3, pp.476-489, 2009.
DOI : 10.1016/j.dam.2008.05.030
URL : https://hal.archives-ouvertes.fr/hal-00354684

]. G. Dan98 and . Dantzig, Linear Programming and extensions, 1998.

]. H. Dav92 and . Davenport, The higher arithmetic : an introduction to the theory of numbers, 1992.

]. M. De-berg, O. Schwarzkopf, M. Van-kreveld, and M. Overmars, Computational Geometry : Algorithms and Applications, 2000.

J. [. Dobkin and . Munro, Efficient uses of the past, FOCS, pp.200-206, 1980.

L. [. Dobkin and . Snyder, On a general method for maximizing and minimizing among certain geometric problems, 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pp.9-17, 1979.
DOI : 10.1109/SFCS.1979.28

]. M. Dye80 and . Dyer, A simplified o(n log n) algorithm for the intersection of 3- polyedra, 1980.

S. [. Eisenbrand and . Laue, A linear algorithm for integer programming in the plane, Mathematical Programming, vol.20, issue.2, pp.249-259, 2005.
DOI : 10.1007/s10107-004-0520-0

G. [. Eisenbrand and . Rote, Fast 2-Variable Integer Programming, Integer Programming and Combinatorial Optimization, pp.78-89, 2001.
DOI : 10.1007/3-540-45535-3_7

]. T. Fer09 and . Fernique, Generation and recognition of digital planes using multidimensional continued fractions, Pattern Recognition, vol.42, issue.10, pp.2229-2238, 2009.

]. F. Fes06 and . Feschet, The exact lattice width of planar sets and minimal arithmetical thickness, Lecture Notes in Computer Science, vol.4040, pp.25-33, 2006.

]. F. Fes08 and . Feschet, The lattice width and quasi-straightness in digital spaces, 19th International Conference on Pattern Recognition (ICPR), pp.1-4, 2008.

]. R. Fmr-+-92, K. Fleischer, G. Mehlhorn, E. Rote, C. Welzl et al., Simultaneous inner and outer approximation of shapes, Algorithmica, vol.8, issue.5&6, pp.365-389, 1992.

J. [. Françon, M. Schramm, and . Tajine, Recognizing arithmetic straight lines and planes, DGCI'96, pp.141-150, 1996.
DOI : 10.1007/3-540-62005-2_12

B. [. Flajolet and . Vallée, Continued fraction algorithms, functional operators, and structure constants, Theoretical Computer Science, vol.194, issue.1-2, pp.1-34, 1998.
DOI : 10.1016/S0304-3975(97)00123-0
URL : https://hal.archives-ouvertes.fr/inria-00073768

Y. Gérard, I. Debled-rennesson, and P. Zimmermann, An elementary digital plane recognition algorithm, Discrete Applied Mathematics, vol.151, issue.1-3, pp.169-183, 2005.
DOI : 10.1016/j.dam.2005.02.026

T. [. Gärtner and . Herrmann, Computing the width of a point set in 3-space

R. L. Graham, D. E. Knuth, O. L. Patashnikgra72-]-r, . J. Grahamgre79-]-p, . Greenhar99-]-w et al., Constructing the convex hull of a set of point in the plane Partitions of mass-distributions and of convex bodies by hyperplanes Computing two-dimensional Integer Hulls Determination of the convex hull of a finite set of planar points within linear time The vertices of the knapasack polytope Computing the width of a set A polynomial-time algorithm for the knapsack problem with two variables On the identification of the convex hull of a finite set of points in the plane The complexity of incremental convex hull algorithms in rd A polynomial algorithm for the two variable integer programming problem Digital planar surface segmentation using local geometric patterns Discrete plane segmentation and estimation from a point cloud using local geometric patterns, Concrete Mathematics : A foundation for computer scienceKar84] N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica DGCI Euro-Pat, pp.132-133262, 1907.

A. G. Kirkpatrick and R. Seidel, The Ultimate Planar Convex Hull Algorithm?, SIAM Journal on Computing, vol.15, issue.1, pp.287-299, 1968.
DOI : 10.1137/0215021

C. E. Kim and I. Stojmenovic, On the recognition of digital planes in threedimensional space, pp.665-669, 1991.

C. [. Kaib and . Schnörr, The Generalized Gauss Reduction Algorithm, Journal of Algorithms, vol.21, issue.3, pp.565-578, 1996.
DOI : 10.1006/jagm.1996.0059

]. R. Ksv96, I. Klette, J. Stojmenovic, ]. G. Zuniclac98a, and . Lachaud, A parametrization of digital planes by least-squares fits and generalizations Klein polygons and geometric diagrams, Graph. Models Image Process. Contemporary Math, vol.58, issue.210, pp.295-300365, 1996.

]. G. Lac98b and . Lachaud, Sails and klein polyhedra, Contemporary Math, vol.210, pp.373-385, 1998.

]. H. Len83 and . Lenstra, Integer Programming with a Fixed Number of Variables, Math. Oper. Research, vol.8, pp.535-548, 1983.

B. [. Lyashko and . Rublev, Minimal Ellipsoids and Maximal Simplexes in 3D Euclidean Space, Cybernetics and Systems Analysis, vol.39, issue.6, pp.831-834, 2003.
DOI : 10.1023/B:CASA.0000020224.83374.d7

]. G. Mat97 and . Mathews, On the partition of numbers, pp.486-490, 1897.

]. N. Meg84 and . Megiddo, Linear programming in linear time when the dimension is fixed

]. A. Mel87 and . Melkman, On-line construction of the convex hull of a simple polyline

]. F. Mor02 and . Mora, Solving polynomial equation systems. I : The Kronecker-Duval philosophy, 2002.

]. K. Mul94 and . Mulmuley, Computational geometry : An introduction through randomized algorithms, 1994.

]. B. Neu45 and . Neumann, On an invariant of plane regions and mass distributions, Journ. London Math. Soc, vol.20, pp.226-237, 1945.

. [. O-'rourke, Computational Geometry in C, 1998.

]. A. Ost22 and . Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen, Abh. Math. Sem. Hamburg, vol.1, pp.77-98250, 1922.

L. [. Provot, Buzer, and I. Debled-Rennesson. Recognition of blurred pieces of discrete planes, DGCI, pp.65-76, 2006.

S. [. Preparata and . Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, vol.20, issue.2, pp.87-93, 1977.
DOI : 10.1145/359423.359430

]. G. Pic99 and . Pick, Geometrisches zur zahlentheorie, Sitzenber. Lotos, vol.19, pp.311-319, 1899.

F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, vol.22, issue.7, pp.402-405, 1979.
DOI : 10.1145/359131.359132

M. [. Preparata and . Shamos, Computational Geometry : an Introduction, 1985.
DOI : 10.1007/978-1-4612-1098-6

]. [-rev91 and . Reveilì-es, Géométrie discrète, calcul en nombres entiers et algorithmique, Thèse d'´ etat, 1991.

]. [-rev95 and . Reveilì-es, Combinatorial pieces in digital lines and planes, Vision Geometry IV, SPIE 2573, pp.23-34, 1995.

]. A. Ros70 and . Rosenfeld, Connectivity in digital pictures, J. ACM, vol.17, issue.1, pp.146-160, 1970.

]. G. Rot97 and . Rote, Finding a shortest vector in a two-dimensional lattice modulo m, Theoretical Computer Science, vol.172, issue.12, pp.303-308, 1997.

]. H. Sca81 and . Scarf, Production sets with indivisibilities part i and part ii, Econometrica, vol.49, pp.1-32, 1981.

]. J. Sha94 and . Shallit, Origins of the analysis of the euclidean algorithm, Historica Mathematica, vol.21, pp.401-419, 1994.

R. [. Stojmenovic and . Tosic, Digitization schemes and the recognition of digital straight lines, hyperplanes, and flats in arbitrary dimensions, Contemporary Mathematics Series, vol.119, pp.197-212, 1991.
DOI : 10.1090/conm/119/1113909

]. S. Ste01 and . Stefanov, Separable Programming, Theory and Methods, volume 53 of Applied Optimization, 2001.

]. G. Tou83 and . Toussaint, Solving geometric problems with the rotating calipers, Proc. IEEE MELECON '83, pp.10-12, 1983.

J. [. Vittone and . Chassery, Recognition of Digital Naive Planes and Polyhedrization, DGCI '00 : Proceedings of the 9th International Conference on Discrete Geometry for Computer Imagery, pp.296-307, 2000.
DOI : 10.1007/3-540-44438-6_25

]. P. Vee93 and . Veelaert, On the flatness of digital hyperplanes, JMIV, vol.3, pp.205-221, 1993.

]. P. Vee94 and . Veelaert, Digital planarity of rectangular surface segments, IEEE Trans. Pattern Anal. Mach. Intell, vol.16, issue.6, pp.647-652, 1994.

]. L. Vui98 and . Vuillon, Combinatoire des motifs d'une suite sturmienne bidimensionnelle, TCS, vol.209, pp.261-285, 1998.

]. N. Zol00 and . Zolotykh, On the number of vertices in integer linear programming problems, 2000.