Combinatorial generation of planar sets. (English) Zbl 07753636
Summary: We introduce a multi-dimensional generalization of the Euclidean algorithm and show how it is related to digital geometry and particularly to the generation and recognition of digital planes. We show how to associate with the steps of the algorithm geometrical extensions of substitutions, i.e., rules that replace faces by unions of faces, to build finite sets called patterns. We examine several of their combinatorial, geometrical and topological properties. This work is a first step toward the incremental computation of patterns that locally fit a digital surface for the accurate approximation of tangent planes.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
Euclidean algorithm; continued fractions; digital geometry; digital plane; substitutions; plane-probing algorithmsReferences:
| [1] | Reveillès, J.-P.: Géométrie discrète, calculs en nombres entiers et algorithmique. Thèse d’etat, Université Louis Pasteur (1991) · Zbl 1079.51513 |
| [2] | Françon, J., Schramm, J.-M., Tajine, M.: Recognizing arithmetic straight lines and planes. In: Proc. DGCI, pp. 139-150 (1996) · Zbl 1541.68418 |
| [3] | Brimkov, V.; Coeurjolly, D.; Klette, R., Digital planarity—a review, Discret. Appl. Math., 155, 4, 468-495 (2007) · Zbl 1109.68122 · doi:10.1016/j.dam.2006.08.004 |
| [4] | Lachaud, J-O; Meyron, J.; Roussillon, T., An optimized framework for plane-probing algorithms, J. Math. Imaging Vis., 62, 718-736 (2020) · Zbl 1482.68253 · doi:10.1007/s10851-020-00965-6 |
| [5] | Lachaud, J-O; Provençal, X.; Roussillon, T., Two plane-probing algorithms for the computation of the normal vector to a digital plane, J. Math. Imaging Vis., 59, 23-39 (2017) · Zbl 1422.68247 · doi:10.1007/s10851-017-0704-x |
| [6] | Troesch, A., Interprétation géométrique de l’algorithme d’Euclide et reconnaissance de segments, Theor. Comput. Sci., 115, 2, 291-319 (1993) · Zbl 0774.68103 · doi:10.1016/0304-3975(93)90121-9 |
| [7] | Klette, R.; Rosenfeld, A., Digital straightness—a review, Discret. Appl. Math., 139, 1-3, 197-230 (2004) · Zbl 1093.68656 · doi:10.1016/j.dam.2002.12.001 |
| [8] | Labbé, S.; Reutenauer, C., A d-dimensional extension of Christoffel words, Discret. Comput. Geom., 54, 1, 152-181 (2015) · Zbl 1317.05161 · doi:10.1007/s00454-015-9681-2 |
| [9] | Berthé, V., Fernique, T.: Brun expansions of stepped surfaces. Discret. Math. 311(7), 521-543 (2011) · Zbl 1236.11011 |
| [10] | Berthé, V.; Lacasse, A.; Paquin, G.; Provençal, X., A study of Jacobi-Perron boundary words for the generation of discrete planes, Theor. Comput. Sci., 502, 118-142 (2013) · Zbl 1296.68113 · doi:10.1016/j.tcs.2012.03.045 |
| [11] | Berthé, V., Domenjoud, É., Jamet, D., Provençal, X.: Fully Subtractive algorithm, tribonacci numeration and connectedness of discrete planes. Research Institute for Mathematical Sciences, Lecture note Kokyuroku Bessatu B, vol. 46, pp. 159-174 (2014) · Zbl 1352.11013 |
| [12] | Jamet, D., Lafrenière, N., Provençal, X.: Generation of digital planes using generalized continued-fractions algorithms. In: Proc. DGCI, pp. 45-56 (2016) · Zbl 1430.94021 |
| [13] | Berthé, V., Jamet, D., Jolivet, T., Provençal, X.: Critical connectedness of thin arithmetical discrete planes. In: Proc. DGCI, pp. 107-118 (2013) · Zbl 1382.68246 |
| [14] | Domenjoud, E.; Vuillon, L., Geometric palindromic closure, Uniform Distrib. Theory, 7, 2, 109-140 (2012) · Zbl 1324.68071 |
| [15] | Domenjoud, E., Laboureix, B., Vuillon, L.: Facet connectedness of arithmetic discrete hyperplanes with non-zero shift. In: Proc. DGCI (2019) · Zbl 1522.68644 |
| [16] | Domenjoud, E., Provençal, X., Vuillon, L.: Facet connectedness of discrete hyperplanes with zero intercept: the general case. In: Proc. DGCI, pp. 1-12 (2014) · Zbl 1419.68194 |
| [17] | Arnoux, P.; Ito, S., Pisot substitutions and Rauzy fractals, Bull. Belgian Math. Soc. Simon Stevin, 8, 2, 181-208 (2001) · Zbl 1007.37001 · doi:10.36045/bbms/1102714169 |
| [18] | Fernique, T., Multidimensional Sturmian sequences and generalized substitutions, Int. J. Found. Comput. Sci., 17, 575-600 (2006) · Zbl 1096.68125 · doi:10.1142/S0129054106004005 |
| [19] | Fernique, T., Generation and recognition of digital planes using multi-dimensional continued fractions, Pattern Recogn., 42, 10, 2229-2238 (2009) · Zbl 1176.68180 · doi:10.1016/j.patcog.2008.11.003 |
| [20] | Meyron, J., Roussillon, T.: Approximation of Digital Surfaces by a Hierarchical Set of Planar Patches. In: IAPR Second International Conference on Discrete Geometry and Mathematical Morphology, Strasbourg, France, pp. 409-421 (2022) · Zbl 1522.68662 |
| [21] | Labbé, S.: \(3 \)-dimensional continued fraction algorithms cheat sheets. arXiv:1511.08399 (2015) |
| [22] | Lu, J.-T., Roussillon, T., Coeurjolly, D.: A New Lattice-based Plane-probing Algorithm. In: IAPR Second International Conference on Discrete Geometry and Mathematical Morphology, Strasbourg, France (2022) |
| [23] | Roussillon, T., Lu, J.-T., Lachaud, J.-O., Coeurjolly, D.: Delaunay property and proximity results of the L-algorithm. Research report, Université de Lyon (2022). https://hal.archives-ouvertes.fr/hal-03719592 |
| [24] | Arnoux, P.; Furukado, M.; Harriss, E.; Ito, S., Algebraic numbers, free group automorphisms and substitutions on the plane, Trans. Am. Math. Soc., 363, 4651-4699 (2011) · Zbl 1254.37015 · doi:10.1090/S0002-9947-2011-05188-3 |
| [25] | Jolivet, T.: Combinatorics of Pisot Substitutions. Ph.d. thesis, Université Paris Diderot, University of Turku. https://jolivet.org/timo/docs/thesis_jolivet.pdf (2013) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
