Run-hierarchical structure of digital lines with irrational slopes in terms of continued fractions and the Gauss map
2009 (English)In: Pattern Recognition, ISSN 0031-3203, E-ISSN 1873-5142, Vol. 42, no 10, 2247-2254 p.Article in journal (Refereed) Published
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.
digital geometry, digital line, irrational slope, continued fraction, quadratic surd, Gauss map
Research subject Mathematics
IdentifiersURN: urn:nbn:se:uu:diva-105924DOI: 10.1016/j.patcog.2008.11.005ISI: 000267472800005OAI: oai:DiVA.org:uu-105924DiVA: diva2:222871