uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Run-hierarchical structure of digital lines with irrational slopes in terms of continued fractions and the Gauss map
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics. (Digital geometry and mathematical morphology)
2009 (English)In: Pattern Recognition, ISSN 0031-3203, E-ISSN 1873-5142, Vol. 42, no 10, 2247-2254 p.Article in journal (Refereed) Published
Abstract [en]

We study relations between digital lines and continued fractions. The main result is a parsimonious description of the construction of the digital line based only on the elements of the continued fraction representing its slope and containing only simple integer computations. The description reflects the hierarchy of digitization runs, which raises the possibility of dividing digital lines into equivalence classes depending on the continued fraction expansions of their slopes. Our work is confined to irrational slopes since, to our knowledge,there exists no such description for these, in contrast to rational slopes which have been extensively examined. The description is exact (it does not use approximations by rationals). Examples of lines with irrational slopes and with very simple digitization patterns are presented. These include both slopes with periodic and non-periodic continued fraction expansions, i.e.\ both quadratic surds and other irrationals. We also derive the connection between the Gauss map and the digitization parameters introduced by the author in 2007.

Place, publisher, year, edition, pages
Elsevier , 2009. Vol. 42, no 10, 2247-2254 p.
Keyword [en]
digital geometry, digital line, irrational slope, continued fraction, quadratic surd, Gauss map
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-105924DOI: 10.1016/j.patcog.2008.11.005ISI: 000267472800005OAI: oai:DiVA.org:uu-105924DiVA: diva2:222871
Available from: 2009-06-09 Created: 2009-06-09 Last updated: 2017-12-13Bibliographically approved
In thesis
1. Digital lines, Sturmian words, and continued fractions
Open this publication in new window or tab >>Digital lines, Sturmian words, and continued fractions
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we present and solve selected problems arising from digital geometry and combinatorics on words. We consider digital straight lines and, equivalently, upper mechanical words with positive irrational slopes a<1 and intercept 0. We formulate a continued fraction (CF) based description of their run-hierarchical structure.

Paper I gives a theoretical basis for the CF-description of digital lines. We define for each irrational positive slope less than 1 a sequence of digitization parameters which fully specifies the run-hierarchical construction.

In Paper II we use the digitization parameters in order to get a description of runs using only integers. We show that the CF-elements of the slopes contain the complete information about the run-hierarchical structure of the line. The index jump function introduced by the author indicates for each positive integer k the index of the CF-element which determines the shape of the digitization runs on level k.

In Paper III we present the results for upper mechanical words and compare our CF-based formula with two well-known methods, one of which was formulated by Johann III Bernoulli and proven by Markov, while the second one is known as the standard sequences method. Due to the special treatment of some CF-elements equal to 1 (essential 1's in Paper IV), our method is currently the only one which reflects the run-hierarchical structure of upper mechanical words by analogy to digital lines.

In Paper IV we define two equivalence relations on the set of all digital lines with positive irrational slopes a<1. One of them groups into classes all the lines with the same run length on all digitization levels, the second one groups the lines according to the run construction in terms of long and short runs on all levels. We analyse the equivalence classes with respect to minimal and maximal elements. In Paper V we take another look at the equivalence relation defined by run construction, this time independently of the context, which makes the results more general.

In Paper VI we define a run-construction encoding operator, by analogy with the well-known run-length encoding operator. We formulate and present a proof of a fixed-point theorem for Sturmian words. We show that in each equivalence class under the relation based on run length on all digitization levels (as defined in Paper IV), there exists exactly one fixed point of the run-construction encoding operator.

Place, publisher, year, edition, pages
Uppsala: Matematiska institutionen, 2009. 59 p.
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 65
Keyword
digital geometry, digital line, hierarchy of runs, combinatorics on words, Sturmian word, upper mechanical word, characteristic word, irrational slope, continued fraction, Gauss map, fixed point
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:uu:diva-107274 (URN)978-91-506-2090-0 (ISBN)
Public defence
2009-09-25, Polhemsalen, Lägerhyddsvägen 1, Uppsala, Ångström Laboratory, 10:15 (English)
Opponent
Supervisors
Available from: 2009-09-04 Created: 2009-08-03 Last updated: 2009-09-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Uscka-Wehlou, Hanna

Search in DiVA

By author/editor
Uscka-Wehlou, Hanna
By organisation
Department of Mathematics
In the same journal
Pattern Recognition
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 603 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf