Search

Your search keyword '"Discrete plane"' showing total 34 results
Start Over Descriptor "Discrete plane" Search Limiters Available in Library Collection
34 results on '"Discrete plane"'

1. Lost in self-stabilization: A local process that aligns connected cells.

Author

Regnault, Damien and Rémila, Éric

Subjects
*CELLS, *INTEGERS, *PARAMETERS (Statistics), *CELLULAR automata, *CRYSTALLOGRAPHY
Abstract

Let t a and t b be a pair of relatively prime positive integers. We work on chains of n ( t a + t b ) agents which form together an upper and rightward directed path of the grid Z 2 from O = ( 0 , 0 ) to M = ( n t a , n t b ) . We are interested on evolution rules such that, at each time step, an agent is randomly chosen on the chain and is allowed to jump to another site of the grid preserving the connectivity of the chain and the endpoints. The rules must be local, i.e. , the decision of jumping or not only depends on the neighborhood of fixed size s of the randomly chosen agent, and not on the parameters t a , t b , n . Moreover, the parameter s only depends on t a + t b and not on n . In this paper, we design a rule such that, starting from any chain which does not cross the continuous line segment [ O , M ] , this rule reorganizes this chain into one of the best possible approximations of [ O , M ] . The stabilization is reached after O ( ( n ( t a + t b ) ) 4 ) iterations, in average. The work presented here is at the crossroad of many different domains such as modeling a stabilizing process in crystallography, stochastic cellular automata, organizing a line of robots in distributed algorithms (the robot chain problem) and Christoffel words in language theory. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

2. A study of Jacobi–Perron boundary words for the generation of discrete planes.

Author

Berthé, Valérie, Lacasse, Annie, Paquin, Geneviève, and Provençal, Xavier

Subjects
*ALGORITHMS, *APPROXIMATION theory, *PATTERNS (Mathematics), *GENERALIZATION, *DIMENSIONAL analysis, *COMPUTATIONAL mathematics
Abstract

Abstract: The construction of a Sturmian word, and thus of a discrete line, from a continued fraction development generalizes to higher dimensions. Given any vector , a list of 6-connected points approximating the line defined by may be obtained via a generalized continued fraction algorithm. By duality, a discrete plane with normal vector can also be generated using a related technique. We focus on such discrete planes, more precisely on the finite patterns generated at each step of the process. We show that the choice of the Jacobi–Perron algorithm as a higher dimension generalization of Euclid’s algorithm together with the specific substitutions deduced from it allows us to guaranty the simple connectedness of those patterns. [Copyright &y& Elsevier]

Published
2013
Full Text
View/download PDF

3. Connectivity of discrete planes

Author

Brimkov, Valentin E. and Barneva, Reneta P.

Subjects
*COMBINATORIAL geometry, *DISCRETE geometry, *TOPOLOGY, *POLYHEDRA
Abstract

Studying connectivity of discrete objects is a major issue in discrete geometry and topology. In the present work, we deal with connectivity of discrete planes in the framework of Réveillès analytical definition (Thèse d’État, Université Louis Pasteur, Strasbourg, France, 1991). Accordingly, a discrete plane is a set P(a,b,c,μ,ω) of integer points (x,y,z) satisfying the Diophantine inequalities 0⩽ax+by+cz+μ<ω. The parameter μ∈Z estimates the plane intercept while ω∈N is the plane thickness. Given three integers (plane coefficients) a,b, and c with 0⩽a⩽b⩽c, one can seek the value of ω beyond which the discrete plane P(a,b,c,μ,ω) is always connected. We call this remarkable topological invariable the connectivity number of P(a,b,c,μ,ω) and denote it Ω(a,b,c). Despite several attempts over the last 10 years to determine the connectivity number, this is still an open question. In the present paper, we propose a solution to the problem. For this, we first investigate some combinatorial properties of discrete planes. These structural results facilitate the deeper understanding of the discrete plane structure. On this basis, we obtain a series of results, in particular, we provide an explicit solution to the problem under certain conditions. We also obtain exact upper and lower bounds on Ω(a,b,c) and design an O(alogb) algorithm for its computation. [Copyright &y& Elsevier]

Published
2004
Full Text
View/download PDF

4. Two-dimensional iterated morphisms and discrete planes

Author

Arnoux, Pierre, Berthé, Valérie, and Siegel, Anne

Subjects
*MORPHISMS (Mathematics), *FORMAL sociology, *ALGEBRA, *ALPHABET
Abstract

Iterated morphisms of the free monoid are very simple combinatorial objects which produce infinite sequences by replacing iteratively letters by words. The aim of this paper is to introduce a formalism for a notion of two-dimensional morphisms; we show that they can be iterated by using local rules, and that they generate two-dimensional patterns related to discrete approximations of irrational planes with algebraic parameters. We associate such a two-dimensional morphism with any usual Pisot unimodular one-dimensional iterated morphism over a three-letter alphabet. [Copyright &y& Elsevier]

Published
2004
Full Text
View/download PDF

5. Representation formula for discrete indefinite affine spheres

Author

Shimpei Kobayashi and Nozomu Matsuura

Subjects
Mathematics - Differential Geometry, Pure mathematics, Tzitzeica equation, Affine sphere, Primary 53A15, 37K10, 01 natural sciences, Loop group, 0103 physical sciences, Decomposition (computer science), FOS: Mathematics, 0101 mathematics, Mathematics, Discrete plane, 010102 general mathematics, Representation (systemics), Loop (topology), Computational Theory and Mathematics, Differential Geometry (math.DG), Liouville equation, SPHERES, 010307 mathematical physics, Geometry and Topology, Affine transformation, Discrete integrable systems, Analysis, Discrete differential geometry
Abstract

We present a representation formula for discrete indefinite affine spheres via loop group factorizations. This formula is derived from the Birkhoff decomposition of loop groups associated with discrete indefinite affine spheres. In particular we show that a discrete indefinite improper affine sphere can be constructed from two discrete plane curves., 38 pages

Published
2020

6. A discrete version of plane wave solutions of the Dirac equation in the Joyce form

Author

Volodymyr Sushch

Subjects
Discrete plane, Discretization, Applied Mathematics, 010102 general mathematics, Mathematical analysis, Plane wave, FOS: Physical sciences, Mathematical Physics (math-ph), 01 natural sciences, symbols.namesake, 39A12, 39A70, 81Q05, Scheme (mathematics), Dirac equation, 0103 physical sciences, symbols, 010307 mathematical physics, Mathematics::Differential Geometry, 0101 mathematics, Mathematics::Symplectic Geometry, Mathematical Physics, Mathematics
Abstract

We construct a discrete version of the plane wave solution to a discrete Dirac-K\"{a}hler equation in the Joyce form. A geometric discretisation scheme based on both forward and backward difference operators is used. The conditions under which a discrete plane wave solution satisfies a discrete Joyce equation are discussed., Comment: 20 pages. arXiv admin note: substantial text overlap with arXiv:1802.00040

Published
2019

7. Dual substitutions over $mathbb{R}_{>0}-$powered symbols (Natural extension of arithmetic algorithms and S-adic system)

Author

Tamura, Jun-ichi and Yasutomi, Shin-ichi

Subjects
37B10, discrete plane, substitution, 0}-%24powered+symbols%22">substitution over $mathbb{R}_{>0}-$powered symbols, 68R15, dual substitution, substitution over p stepped surface
Abstract

We will consider dual substitutions of substitutions over R>0-powered symbols which are introduced in [12]. We give a class of weighted substitutions including the dual substitutions. We also introduce weighted tips which generalize the unit tip in a stepped surface (discrete plane)., "Natural extension of arithmetic algorithms and S-adic system". July 20～24, 2015. edited by Shigeki Akiyama. The papers presented in this volume of RIMS Kôkyûroku Bessatsu are in final form and refereed.

Published
2016

8. Lost in self-stabilization: A local process that aligns connected cells

Author

Damien Regnault, Eric Rémila, Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne (GATE Lyon Saint-Étienne), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Groupe d'analyse et de théorie économique (GATE Lyon Saint-Étienne), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université Lumière - Lyon 2 (UL2)-École normale supérieure - Lyon (ENS Lyon)

Subjects
Self-organization, Cellular automata, Christoffel symbols, General Computer Science, Coprime integers, Self-stabilization, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 01 natural sciences, Theoretical Computer Science, Combinatorics, Stochastic cellular automaton, Line segment, Chain (algebraic topology), 010201 computation theory & mathematics, Path (graph theory), Line (geometry), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Mathematics, Discrete plane
Abstract

Let t a and t b be a pair of relatively prime positive integers. We work on chains of n ( t a + t b ) agents which form together an upper and rightward directed path of the grid Z 2 from O = ( 0 , 0 ) to M = ( n t a , n t b ) . We are interested on evolution rules such that, at each time step, an agent is randomly chosen on the chain and is allowed to jump to another site of the grid preserving the connectivity of the chain and the endpoints. The rules must be local, i.e., the decision of jumping or not only depends on the neighborhood of fixed size s of the randomly chosen agent, and not on the parameters t a , t b , n . Moreover, the parameter s only depends on t a + t b and not on n. In this paper, we design a rule such that, starting from any chain which does not cross the continuous line segment [ O , M ] , this rule reorganizes this chain into one of the best possible approximations of [ O , M ] . The stabilization is reached after O ( ( n ( t a + t b ) ) 4 ) iterations, in average. The work presented here is at the crossroad of many different domains such as modeling a stabilizing process in crystallography, stochastic cellular automata, organizing a line of robots in distributed algorithms (the robot chain problem) and Christoffel words in language theory.

Published
2018
Full Text
View/download PDF

9. 数系と置換規則（Numeration and Substitution）2012

Author

BERTHE, Valerie, DOMENJOUD, Eric, JAMET, Damien, and PROVENCAL, Xavier

Subjects
11A63, $bata$-numeration, discrete plane, discrete connectivity, MSC: 68R01, Tribonacci number
Abstract

"Numeration and Substitution 2012. June 4～8, 2012". edited by Shigeki Akiyama, Valerie Berthe, Hui Rao and Takao Komatsu. The papers presented in this volume of RIMS Kokyuroku Bessatsu are in final form and refereed.

Published
2014

11. Weak colored local rules for planar tilings

Author

Thomas Fernique, Mathieu Sablik, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), ANR-12-JS02-0011,QuasiCool,Refroidissement des quasicristaux : des pavages aléatoires aux pavages apériodiques(2012), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), and Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 37B50, 52C23, 03D80, 37B10, Discrete Mathematics (cs.DM), discrete plane, General Mathematics, Existential quantification, Dynamical Systems (math.DS), Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Set (abstract data type), Combinatorics, Planar, local rules, 0103 physical sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, 0101 mathematics, Algebraic number, Mathematics - Dynamical Systems, Finite set, Mathematics, Applied Mathematics, 010102 general mathematics, cut and project, Linear subspace, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Colored, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, 010307 mathematical physics, Tiling, Computer Science - Discrete Mathematics
Abstract

A linear subspace $E$ of $\mathbb{R}^n$ has colored local rules if there exists a finite set of decorated tiles whose tilings are digitizations of $E$. The local rules are weak if the digitizations can slightly wander around $E$. We prove that a linear subspace has weak colored local rules if and only if it is computable. This goes beyond the previous results, all based on algebraic subspaces. We prove an analogous characterization for sets of linear subspaces, including the set of all the linear subspaces of $\mathbb{R}^n$., 30 pages, 10 figures

Published
2016
Full Text
View/download PDF

12. Isogonal deformation of discrete plane curves and discrete Burgers hierarchy

Author

Nozomu Matsuura, Toshinobu Kuroda, and Kenji Kajiwara

Subjects
Nonlinear Sciences - Exactly Solvable and Integrable Systems, Hierarchy (mathematics), Isogonal figure, Deformation (mechanics), Discrete plane, Plane curve, Mathematical finance, 010102 general mathematics, Mathematical analysis, FOS: Physical sciences, Geometry, 01 natural sciences, Smooth curves, Nonlinear Sciences::Exactly Solvable and Integrable Systems, 0103 physical sciences, Exactly Solvable and Integrable Systems (nlin.SI), 0101 mathematics, 010306 general physics, Differential (mathematics), Mathematics
Abstract

We study deformations of plane curves in the similarity geometry. It is known that continuous deformations of smooth curves are described by the Burgers hierarchy. In this paper, we formulate the discrete deformation of discrete plane curves described by the discrete Burgers hierarchy as isogonal deformations. We also construct explicit formulas for the curve deformations by using the solution of linear diffusion differential/difference equations.

Published
2016
Full Text
View/download PDF

13. MOTION AND B^|^Auml;CKLUND TRANSFORMATIONS OF DISCRETE PLANE CURVES

Author

Nozomu Matsuura, Yasuhiro Ohta, Jun-ichi Inoguchi, and Kenji Kajiwara

Subjects
Discrete plane, General Mathematics, Mathematical analysis, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Motion (geometry), Function (mathematics), Construct (python library), Transformation theory, ComputingMethodologies_COMPUTERGRAPHICS, Mathematics
Abstract

We construct explicit solutions to discrete motion of discrete plane curves which has been introduced by one of the authors recently. Explicit formulas in terms the function are presented. Transformation theory of motions of both smooth and discrete curves is developed simultaneously.

Published
2012
Full Text
View/download PDF

14. A combinatorial approach to products of Pisot substitutions

Author

Valérie Berthé, Anne Siegel, Jérémie Bourdon, Timo Jolivet, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Dynamics, Logics and Inference for biological Systems and Sequences (Dyliss), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Pure mathematics, Discrete plane, Dynamical systems theory, Applied Mathematics, General Mathematics, 010102 general mathematics, ta111, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], 02 engineering and technology, DUAL (cognitive architecture), 01 natural sciences, Coincidence, Discrete spectrum, Fractal, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, 020201 artificial intelligence & image processing, Fraction (mathematics), 0101 mathematics, Mathematics - Dynamical Systems, Focus (optics), Mathematics, Computer Science - Discrete Mathematics
Abstract

We define a generic algorithmic framework to prove pure discrete spectrum for the substitutive symbolic dynamical systems associated with some infinite families of Pisot substitutions. We focus on the families obtained as finite products of the three-letter substitutions associated with the multidimensional continued fraction algorithms of Brun and Jacobi-Perron. Our tools consist in a reformulation of some combinatorial criteria (coincidence conditions), in terms of properties of discrete plane generation using multidimensional (dual) substitutions. We also deduce some topological and dynamical properties of the Rauzy fractals, of the underlying symbolic dynamical systems, as well as some number-theoretical properties of the associated Pisot numbers., Comment: 32 pages, v2 with many corrections and improvements

Published
2016
Full Text
View/download PDF

15. Discrete planes, ${\Bbb Z}^2$-actions, Jacobi-Perron algorithm and substitutions

Author

Pierre Arnoux, Shunji Ito, and Valérie Berthé

Subjects
Combinatorics, Linear algorithm, symbols.namesake, Algebra and Number Theory, Number theory, Discrete plane, symbols, Jacobi method, Geometry, Geometry and Topology, Rauzy fractal, Mathematics
Abstract

Nous definissons des substitutions bi-dimensionnelles ; ces substitutions engendrent des suites doubles reliees a des approximations discretes de plans irrationnels. Elles sont obtenues au moyen de l'algorithme classique de Jacobi Perron, en definissant l'induction d'une action de Z 2 par rotations sur le cercle. On donne ainsi une interpretation geometrique nouvelle de l'algorithme de Jacobi-Perron, comme application operant sur l'espace des parametres des actions de Z 2 par rotations.

Published
2002
Full Text
View/download PDF

16. SALIENT POINTS OF Q-CONVEX SETS

Author

Alain Daurat

Subjects
Discrete plane, business.industry, Regular polygon, Topology, Convexity, Set (abstract data type), Combinatorics, Intersection, Artificial Intelligence, Salient, Salient point, Computer Vision and Pattern Recognition, Artificial intelligence, business, Software, Mathematics
Abstract

The Q-convexity is a kind of convexity in the discrete plane. This notion has practically the same properties as the usual convexity: an intersection of two Q-convex sets is Q-convex, and the salient points can be defined like the extremal points. Moreover a Q-convex set is characterized by its salient point. The salient points can be generalized to any finite subset of ℤ2.

Published
2001
Full Text
View/download PDF

17. Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences

Author

Laurent Vuillon and Valérie Bertheacute

Subjects
Discrete mathematics, Combinatorics on words, Plane (geometry), Generalization, Z2-action, Symbolic dynamics, Torus, Theoretical Computer Science, Combinatorics, Unit circle, Discrete Mathematics and Combinatorics, Complexity function, Rectangle, Generalized Sturmian sequences, Discrete plane, Mathematics
Abstract

We study a two-dimensional generalization of Sturmian sequences corresponding to an approximation of a plane: these sequences are defined on a three-letter alphabet and code a two-dimensional tiling obtained by projecting a discrete plane. We show that these sequences code a Z 2 -action generated by two rotations on the unit circle. We first deduce a new way of computing the rectangle complexity function. Then we provide an upper bound on the number of frequencies of rectangular factors of given size.

Published
2000
Full Text
View/download PDF

18. Crossing Numbers and Hard Erdős Problems in Discrete Geometry

Author

László A. Székely

Subjects
Statistics and Probability, Discrete mathematics, Combinatorics, Computational Theory and Mathematics, Discrete plane, Applied Mathematics, Discrete geometry, Mathematical proof, Upper and lower bounds, Graph, Theoretical Computer Science, Mathematics
Abstract

We show that an old but not well-known lower bound for the crossing number of a graph yields short proofs for a number of bounds in discrete plane geometry which were considered hard before: the number of incidences among points and lines, the maximum number of unit distances among n points, the minimum number of distinct distances among n points.

Published
1997
Full Text
View/download PDF

19. Generating discrete planes with substitutions

Author

Valérie Berthé, Anne Siegel, Jérémie Bourdon, Timo Jolivet, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Dynamics, Logics and Inference for biological Systems and Sequences (Dyliss), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Unimodular matrix, Discrete plane, 010201 computation theory & mathematics, 010102 general mathematics, Fraction (mathematics), 0102 computer and information sciences, 0101 mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Finite set, Dual (category theory), Mathematics
Abstract

International audience; Given a finite set S of unimodular Pisot substitutions, we provide a method for characterizing the infinite sequences over S that allow to generate a full discrete plane when, starting from a finite seed, we iterate the multidimensional dual substitutions associated with S. We apply our results to study the substitutions associated with the Brun multidimensional continued fraction algorithm.

Published
2013

20. Critical connectedness of thin arithmetical discrete planes

Author

Xavier Provençal, Valérie Berthé, Damien Jamet, Timo Jolivet, Provençal, Xavier, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Applying Discrete Algorithms to Genomics and Imagery (ADAGIO), Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Mathématiques (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Social connectedness, Geometry, 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Arithmetic function, Fraction (mathematics), 0101 mathematics, Mathematics, Subtractive color, Discrete plane, 010102 general mathematics, Mathematical analysis, Infimum and supremum, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, Combinatorics (math.CO), Critical thickness, Computer Science - Discrete Mathematics
Abstract

An arithmetical discrete plane is said to have critical connecting thickness if its thickness is equal to the infimum of the set of values that preserve its $2$-connectedness. This infimum thickness can be computed thanks to the fully subtractive algorithm. This multidimensional continued fraction algorithm consists, in its linear form, in subtracting the smallest entry to the other ones. We provide a characterization of the discrete planes with critical thickness that have zero intercept and that are $2$-connected. Our tools rely on the notion of dual substitution which is a geometric version of the usual notion of substitution acting on words. We associate with the fully subtractive algorithm a set of substitutions whose incidence matrix is provided by the matrices of the algorithm, and prove that their geometric counterparts generate arithmetic discrete planes., Comment: 18 pages, v2 includes several corrections and is a long version of the DGCI extended abstract

Published
2013

21. Local Rules for Computable Planar Tilings

Author

Mathieu Sablik, Thomas Fernique, Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), ANR-12-JS02-0011,QuasiCool,Refroidissement des quasicristaux : des pavages aléatoires aux pavages apériodiques(2012), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Sablik, Mathieu, and Jeunes Chercheuses et Jeunes Chercheurs - Refroidissement des quasicristaux : des pavages aléatoires aux pavages apériodiques - - QuasiCool2012 - ANR-12-JS02-0011 - JC - VALID

Subjects
FOS: Computer and information sciences, Pure mathematics, Class (set theory), Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), discrete plane, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], Computer Science - Formal Languages and Automata Theory, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Domino, lcsh:QA75.5-76.95, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], local rules, 0103 physical sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, 0101 mathematics, F.1.1, F.1.2, F.1.3, Mathematics, lcsh:Mathematics, 010102 general mathematics, Quasicrystal, cut and project, lcsh:QA1-939, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Computational Complexity, [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], If and only if, Aperiodic graph, Irrational number, Key (cryptography), 010307 mathematical physics, Combinatorics (math.CO), lcsh:Electronic computers. Computer science, Tiling, Vector space, Computer Science - Discrete Mathematics
Abstract

Aperiodic tilings are non-periodic tilings characterized by local constraints. They play a key role in the proof of the undecidability of the domino problem (1964) and naturally model quasicrystals (discovered in 1982). A central question is to characterize, among a class of non-periodic tilings, the aperiodic ones. In this paper, we answer this question for the well-studied class of non-periodic tilings obtained by digitizing irrational vector spaces. Namely, we prove that such tilings are aperiodic if and only if the digitized vector spaces are computable., In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498

Published
2012

22. Geometric Palindromic Closure

Author

Domenjoud, Eric, Vuillon, Laurent, Domenjoud, Eric, Applying Discrete Algorithms to Genomics and Imagery (ADAGIO), Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques (LAMA), Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), and Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], palindromic closure, discrete plane, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], MSC 68R15,52C99, Computer Science::Formal Languages and Automata Theory, Rauzy fractal, Sturmian sequences
Abstract

http://www.boku.ac.at/MATH/udt/vol07/no2/06DomVuillon13-12.pdf; International audience; We define, through a set of symmetries, an incremental construction of geometric objects in Z^d. This construction is directed by a word over the alphabet {1,...,d}. These objects are composed of d disjoint components linked by the origin and enjoy the nice property that each component has a central symmetry as well as the global object. This construction may be seen as a geometric palindromic closure. Among other objects, we get a 3 dimensional version of the Rauzy fractal. For the dimension 2, we show that our construction codes the standard discrete lines and is equivalent to the well known palindromic closure in combinatorics on words.

Published
2012

23. Explicit solutions to the semi-discrete modified KdV equation and motion of discrete plane curves

Author

Kenji Kajiwara, Yasuhiro Ohta, Jun-ichi Inoguchi, and Nozomu Matsuura

Subjects
Statistics and Probability, Mathematics - Differential Geometry, Discrete plane, Nonlinear Sciences - Exactly Solvable and Integrable Systems, Plane curve, Mathematical analysis, FOS: Physical sciences, General Physics and Astronomy, Motion (geometry), Statistical and Nonlinear Physics, Probability and statistics, Function (mathematics), Nonlinear Sciences::Exactly Solvable and Integrable Systems, Differential Geometry (math.DG), Modeling and Simulation, 53A04, 37K25, 37K10, 35Q53, FOS: Mathematics, Limit (mathematics), Exactly Solvable and Integrable Systems (nlin.SI), Korteweg–de Vries equation, Mathematical Physics, Mathematics
Abstract

We construct explicit solutions to continuous motion of discrete plane curves described by a semi-discrete potential modified KdV equation. Explicit formulas in terms the $\tau$ function are presented. B\"acklund transformations of the discrete curves are also discussed. We finally consider the continuous limit of discrete motion of discrete plane curves described by the discrete potential modified KdV equation to motion of smooth plane curves characterized by the potential modified KdV equation.

Published
2011

25. Subshifts as Models for MSO Logic

Author

Guillaume Theyssier, Emmanuel Jeandel, Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)

Subjects
Model theory, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), Symbolic dynamics, 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Order (group theory), ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.5: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines), 0101 mathematics, Mathematics, Discrete mathematics, Discrete plane, Hierarchy (mathematics), Model Theory, 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 16. Peace & justice, Subshift of finite type, Computer Science Applications, Logic in Computer Science (cs.LO), Tilings, Computational Theory and Mathematics, 010201 computation theory & mathematics, Symbolic Dynamics, Separation result, Computer Science - Discrete Mathematics, Information Systems
Abstract

We study the Monadic Second Order (MSO) Hierarchy over colourings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of "pattern counting" subshifts. Conversely, we characterise logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al., Comment: arXiv admin note: substantial text overlap with arXiv:0904.2457

Published
2009
Full Text
View/download PDF

26. Minimal arithmetic thickness connecting discrete planes

Author

Jean-Luc Toutant, Damien Jamet, Laboratoire de Logique, Algorithmique et Informatique (LLAIC1), Université d'Auvergne - Clermont-Ferrand I (UdA), Applying Discrete Algorithms to Genomics and Imagery (ADAGIO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Discrete plane, Social connectedness, Applied Mathematics, Discrete geometry, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, connectedness, Combinatorics, Hyperplane, 010201 computation theory & mathematics, Mathematics::Category Theory, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, 020201 artificial intelligence & image processing, arithmetic discrete planes, Arithmetic, Hardware_ARITHMETICANDLOGICSTRUCTURES, Focus (optics), Normal, Affine arithmetic, Mathematics
Abstract

International audience; While connected arithmetic discrete lines are entirely characterized, only partial results exist for the more general case of arithmetic discrete hyperplanes. In the present paper, we focus on the $3$-dimensional case, that is on arithmetic discrete planes. Thanks to arithmetic reductions on a vector $\vect{n}$, we provide algorithms either to determine whether a given arithmetic discrete plane with $\vect{n}$ as normal vector is connected, or to compute the minimal thickness for which an arithmetic discrete plane with normal vector $\vect{n}$ is connected.

Published
2009
Full Text
View/download PDF

27. On Some Applications of Generalized Functionality for Arithmetic Discrete Planes

Author

Valérie Berthé, Christophe Fiorio, Fabrice Philippe, Damien Jamet, Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université de Montpellier (UM), Applying Discrete Algorithms to Genomics and Imagery (ADAGIO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Discrete plane, 0102 computer and information sciences, 02 engineering and technology, Arithmetic planes, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, law.invention, Combinatorics, Digital planes, Projection (mathematics), 010201 computation theory & mathematics, law, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, Surface structure, Farey sequence, 020201 artificial intelligence & image processing, Cartesian coordinate system, Computer Vision and Pattern Recognition, Functionality of discrete planes, Local configurations, Arithmetic, Mathematics
Abstract

Naive discrete planes are well known to be functional on a coordinate plane. The aim of our paper is to extend the functionality concept to a larger family of arithmetic discrete planes, by introducing suitable projection directions (@a"1,@a"2,@a"3) satisfying @a"1v"[email protected]"2v"[email protected]"3v"3=w. Several applications are considered. We first study certain local configurations, that is, the (m,n)-cubes introduced in Ref. [J. Vittone, J.-M. Chassery, (n,m)-cubes and Farey Nets for Naive Planes Understanding, in: DGCI, 8th International Conference, Lecture Notes in Computer Science, vol. 1568, Springer-Verlag, 1999, pp. 76-87.]. We compute their number for a given (m,n) and study their statistical behaviour. We then apply functionality to formulate an algorithm for generating arithmetic discrete planes, inspired by Debled-Renesson [I. Debled-Renesson, Reconnaissance des Droites et Plans Discrets, These de doctorat, Universite Louis Pasteur, Strasbourg, France, 1995.]. We also prove that an arithmetic discrete plane may be endowed with a combinatorial surface structure, in the spirit of Ref. [Y. Kenmochi, A. Imiyam Combinatorial topologies for discrete planes, in: DGCI, 11th International Conference, DGCI 2003, Lecture Notes in Computer Science, vol. 2886, Springer-Verlag, 2003, pp. 144-153.].

Published
2007
Full Text
View/download PDF

28. Computational aspects of Digital Plane and Hyperplane Recognition

Author

Valentin E. Brimkov, David Coeurjolly, Coeurjolly, David, Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Mathematics Department, University at Buffalo [SUNY] (SUNY Buffalo), and State University of New York (SUNY)-State University of New York (SUNY)

Subjects
Convex hull, Discrete plane, Discrete geometry, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Combinatorics, Combinatorial analysis, Algebra, Digital plane, Hyperplane, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Recognition algorithm, Mathematics
Abstract

International audience; In these note we review some basic approaches and algorithms for discrete plane/hyperplane recognition. We present, analyze, and compare related theoretical and experimental results and discuss on the possibilities for creating algorithms with higher efficiency.

Published
2006

29. On the Language of Standard Discrete Planes and Surfaces

Author

Damien Jamet, Applying Discrete Algorithms to Genomics and Imagery (ADAGIO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), and Jamet, Damien

Subjects
Discrete plane, Generalization, Dual space, Discrete geometry, Image processing, 0102 computer and information sciences, 02 engineering and technology, Diophantine approximation, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, 01 natural sciences, Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Point (geometry), Representation (mathematics), Mathematics
Abstract

International audience; A standard discrete plane is a subset of Z^3 verifying the double Diophantine inequality mu =< ax+by+cz < mu + omega, with (a,b,c) != (0,0,0). In the present paper we introduce a generalization of this notion, namely the (1,1,1)-discrete surfaces. We first study a combinatorial representation of discrete surfaces as two-dimensional sequences over a three-letter alphabet and show how to use this combinatorial point of view for the recognition problem for these discrete surfaces. We then apply this combinatorial representation to the standard discrete planes and give a first attempt of to generalize the study of the dual space of parameters for the latter [VC00].

Published
2004

30. Regular metric: definition and characterization in the discrete plane

Author

Banon, Gerald Jean Francis and Banon, Gerald Jean Francis

Abstract

We say that a metric space is regular if a straight-line (in the metric space sense) passing through the center of a sphere and any other point has at least two diametrically opposite points. Normed vector spaces have this property. Nevertheless, this property might not be satisfied in some metric spaces. In this work, we give a characterization of an integer-valued translation-invariant regular metric defined on the discrete plane, in terms of a symmetric subset B that induces through, what we call, the Minkowski product, a chain of subsets that are morphologically closed with respect to B., Pages: 249-258

Published
2005

31. Local configurations in a discrete plane

Author

Laurent Vuillon

Subjects
Discrete mathematics, Algebra, 11B83, Discrete plane, General Mathematics, Discrete planes, double sequence complexity, symmetric complementary language, 68R15, generalization of Rote and Sturmian sequences, plane partititons, 05A15, Mathematics
Published
1999
Full Text
View/download PDF

32. 9th International Workshop on Combinatorial Image Analysis

Author

Vito Di Gesù, Attila Kuba, and Alberto Del Lungo

Subjects
Discrete plane, Operations research, Computer science, Applied Mathematics, Discrete Mathematics and Combinatorics, Library science
Abstract

The 9th International Workshop on Combinatorial Image Analysis was held between 14 and 16 May, 2003 in Palermo (Italy). Prior meetings took place in Paris (France, 1991), Ube (Japan, 1992), Washington DC (USA, 1994), Lyon (France, 1995), Hiroshima (Japan, 1997), Madras (India, 1999), Caen (France, 2000) and Philadelphia (USA, 2001). The workshop focused on digital topology, discrete tomography, array, graph and parallel grammars, cellular automata, tilings and patterns, combinatorial methods in image analysis, combinatorial problems in the discrete plane, integer-only algorithms for image analysis, and non-conventional computing for image analysis, like genetic algorithms and global optimization. We are very pleased that P. Grirtzmann (Technische Universitat Munchen), Gabor T. Herman (City University of New York) and Reinhard Klette (The University of Auckland) accepted our invitations to speak at the Workshop. These proceedings contain thirty-one papers and they provide an exciting cross-section of current research in our field. The editors would like to thank the valuable work to the members of the program committee: Alfred M. Bruckstein, Technion Israel Institute of Technology, Israel Jean-Marc Chassery, TIMC-IMAG, France Katsushi Inoue, Yamaguchi University, Japan Yung Kong, City University of New York, USA Kenichi Morita, Hiroshima University, Japan Maurice Nivat, LIAFA, FranceMike Reed, Oxford University, UK Rani Siromoney, Madras Christian College, India Patrick S.P. Wang, Northeastern University, USA Gerhard Woeginger, University of Twente, The Netherlands The editors thank also for the technical help given by Cesare Valenti, University of Palermo, Italy Andrea Frosini, University of Siena, Italy Laszlo Nyul, University of Szeged, Hungary Finally, we would like to thank Peter Hammer for inviting us to publish the Workshop's proceedings online as a volume of Electronic Notes in Discrete Mathematics, and for agreeing to devote a special issue of Discrete Applied Mathematics to IWCIA'2003. The DAM special issue will contain a refereed selection of papers submitted by Workshop presenters after the meeting.

Published
2003
Full Text
View/download PDF

33. Covering by squares

Author

Eric Goles and L. Salinas

Subjects
Vertex (graph theory), Discrete mathematics, Covering, General Computer Science, Discrete plane, Discrete geometry, Edge (geometry), Least squares, Theoretical Computer Science, Combinatorics, Non-linear least squares, Tiling, Computer Science(all), Mathematics
Abstract

In this paper we introduce the “do not touch” condition for squares in the discrete plane. We say that two squares “do not touch” if they do not share any vertex or any segment of an edge. Using this condition we define a covering of the discrete plane, the covering can be strong or weak, regular or non-regular. For simplicity, in this article, we will restrict our attention to regular coverings, i.e., only a size is allowed for the squares and all the squares have the same number of adjacent squares. We establish minimal conditions for the existence of a weak or strong regular covering of the discrete plane, and we give a bound for the number of adjacent squares with respect to the size of the squares in the regular covering.

Full Text
View/download PDF

34. Thin discrete triangular meshes

Author

Reneta P. Barneva, Philippe Nehlig, and Valentin E. Brimkov

Subjects
Mesh of triangles, General Computer Science, Discrete plane, Plane (geometry), Discrete geometry, Space (mathematics), Theoretical Computer Science, Combinatorics, Polyhedron, Grid pattern, Discrete triangle, Triangle mesh, Polygon mesh, Mathematics, Computer Science(all)
Abstract

In this paper we present an approach to describe polyhedra by meshes of discrete triangles. The study is based on the theory of arithmetic discrete geometry, (J.-P. Reveilles, Geometrie discrete, calcul en nombres entiers et algorithmique, These d’etat, Universite Louis Pasteur, Strasbourg, December 1991). As distinct from the previous investigations on this topic, the triangles we introduce are parts of the thinnest possible discrete 6-tunnel-free planes, i.e., those that are usually used in practice. Given a plane P in the space, we define a 6-tunnel-free discrete plane, called a regular plane, which appears to be the best approximation to P . Given a mesh of triangles, we propose a method to approximate any triangle by a discrete triangular patch – a portion of a regular plane, and we prove that the resulting triangular mesh is 6-tunnel-free. The properties of the approximation obtained make the suggested approach convenient for practical applications.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results