BibTex RIS Kaynak Göster

A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry

Yıl 2015, Cilt: 2 Sayı: 3, 169 - 190, 14.09.2015
https://doi.org/10.13069/jacodesmath.79416

Öz

The aim of the paper is to bring new combinatorial analytical properties of the Farey diagrams of order $(m,n)$, which are associated to the $(m,n)$-cubes.
The latter are the pieces of discrete planes occurring in discrete geometry, theoretical computer sciences, and combinatorial number theory.
We give a new upper bound for the number of Farey vertices $FV(m,n)$ obtained as intersections points of Farey lines (\cite{khoshnoudiradfarey}):
$$\exists C>0, \forall (m,n)\in\mathbb{N}^{*2},\quad \Big|FV(m,n)\Big| \leq C m^2 n^2 (m+n) \ln^2 (mn)$$
Using it, in particular, we show that the number of $(m,n)$-cubes $\mathcal{U}_{m,n}$ verifies:
$$\exists C>0, \forall (m,n)\in\mathbb{N}^{*2},\quad \Big|\mathcal{U}_{m,n}\Big| \leq C m^3 n^3 (m+n) \ln^2 (mn)$$
which is an important improvement of the result previously obtained in ~\cite{daurat_tajine_zouaoui_afpdpare},
which was a polynomial of degree 8. This work uses combinatorics, graph theory, and elementary and analytical number theory.

Kaynakça

  • D. M. Acketa and J. D. Žunić, On the number of linear partitions of the (m, n)-grid, Inform. Process. Lett., 38(3), 163-168, 1991.
  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
  • T. Asano and N. Katoh, Variants for the hough transform for line detection, Comput. Geom., 6(4), 231-252, 1996.
  • J. M. Chassery, D. Coeurjolly and I. Sivignon, Duality and geometry straightness, characterization and envelope, Discrete Geometry for Computer Imagery, Springer, 1-16, 2006.
  • J. M. Chassery and A. Montanvert, Geometrical representation of shapes and objects for visual perception, Geometric Reasoning for Perception and Action, Springer, 163-182, 1993.
  • A. Daurat, M. Tajine and M. Zouaoui, About the frequencies of some patterns in digital planes application to area estimators, Comput. Graph., 33(1), 11-20, 2009.
  • I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, PhD thesis, 1995.
  • E. Domenjoud, D. Jamet, D. Vergnaud and L. Vuillon, Enumeration formula for (2, n)-cubes in discrete planes, Discrete Appl. Math., 160(15), 2158-2171, 2012.
  • E. Szemerédi and W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica, 3(3-4), 381-392, 1983. A. Hatcher, Topology of http://www.math.cornell.edu/~hatcher/TN/TNpage.html. numbers, Unpublished manuscript, in preparation; see
  • P. Haukkanen and J. K. Merikoski, Asymptotics of the number of threshold functions on a two- dimensional rectangular grid, Discrete Appl. Math., 161(1), 13-18, 2013.
  • W. Hou and C. Zhang, Parallel-beam ct reconstruction based on mojette transform and compressed sensing, International Journal of Computer and Electrical Engineering, 5(1), 83-87, 2013.
  • Y. Kenmochi, L. Buzer, A. Sugimoto and I. Shimizu, Digital planar surface segmentation using local geometric patterns, Discrete Geometry for Computer Imagery, Springer, 322-333, 2008.
  • D. Khoshnoudirad, Farey lines defining Farey diagrams, and application to some discrete structures, Appl. Anal. Discrete Math., 9(1), 73-84, 2015.
  • A. O. Matveev, A note on Boolean lattices and Farey sequences, Integers, 7, A20, 2007.
  • A. O. Matveev, Relative blocking in posets, J. Comb. Optim., 13(4), 379-403, 2007, Corrigendum: arXiv:math/0411026.
  • A. O. Matveev, Neighboring fractions in Farey subsequences, arXiv:0801.1981, 2008.
  • A. O. Matveev, A note on Boolean lattices and Farey sequences II, Integers, 8, A24, 2008.
  • M. D. McIlroy, A note on discrete representation of lines, AT&T Technical Journal, 64(2), 481-490, 19 E. Remy and E. Thiel, Exact medial axis with euclidean distance, Image and Vision Computing, 23(2), 167-175, 2005.
  • E. Remy and E. Thiel, Structures dans les spheres de chanfrein, RFIA, 483-492, 2000.
  • I. Svalbe and A. Kingston, On correcting the unevenness of angle distributions arising from integer ratios lying in restricted portions of the Farey plane, Combinatorial Image Analysis, Springer, 110- 121, 2005.
  • G. Tenenbaum, Introduction to analytic and probabilistic number theory, 46, Cambridge University Press, 1995.
  • E. Thiel, Les distances de chenfrein en analyse d’images : fondements et applications, Thélse de doctorat, UJF Grenoble, 1994.
  • E. Thiel and A. Montanvert, Chamfer masks: Discrete distance functions, geometrical properties and optimization, Pattern Recognition, Vol. III. Conference C: Image, Speech and Signal Analysis, Proceedings., 11th IAPR International Conference on, IEEE, 244-247, 1992.
  • R. Tomás, Asymptotic behavior of a series of Euler’s totient function ϕ(k) times the index of 1/k in a Farey sequence, arXiv:1406.6991, 2014.
  • R. Tomás, From farey sequences to resonance diagrams, Physical Review Special Topics-Accelerators and Beams, 17(1), 014001, 2014.
  • V. Trifonov, L. Pasqualucci, R. Dalla-Favera and R. Rabadan, Fractal-like distributions over the rational numbers in high-throughput biological and clinical data, Scientific reports, 1, 2011.
  • G. H. Hardy and E. M. Wright, Introduction à la théorie des nombres, Traduction de François Sauvageot, Springer.
Yıl 2015, Cilt: 2 Sayı: 3, 169 - 190, 14.09.2015
https://doi.org/10.13069/jacodesmath.79416

Öz

Kaynakça

  • D. M. Acketa and J. D. Žunić, On the number of linear partitions of the (m, n)-grid, Inform. Process. Lett., 38(3), 163-168, 1991.
  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
  • T. Asano and N. Katoh, Variants for the hough transform for line detection, Comput. Geom., 6(4), 231-252, 1996.
  • J. M. Chassery, D. Coeurjolly and I. Sivignon, Duality and geometry straightness, characterization and envelope, Discrete Geometry for Computer Imagery, Springer, 1-16, 2006.
  • J. M. Chassery and A. Montanvert, Geometrical representation of shapes and objects for visual perception, Geometric Reasoning for Perception and Action, Springer, 163-182, 1993.
  • A. Daurat, M. Tajine and M. Zouaoui, About the frequencies of some patterns in digital planes application to area estimators, Comput. Graph., 33(1), 11-20, 2009.
  • I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, PhD thesis, 1995.
  • E. Domenjoud, D. Jamet, D. Vergnaud and L. Vuillon, Enumeration formula for (2, n)-cubes in discrete planes, Discrete Appl. Math., 160(15), 2158-2171, 2012.
  • E. Szemerédi and W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica, 3(3-4), 381-392, 1983. A. Hatcher, Topology of http://www.math.cornell.edu/~hatcher/TN/TNpage.html. numbers, Unpublished manuscript, in preparation; see
  • P. Haukkanen and J. K. Merikoski, Asymptotics of the number of threshold functions on a two- dimensional rectangular grid, Discrete Appl. Math., 161(1), 13-18, 2013.
  • W. Hou and C. Zhang, Parallel-beam ct reconstruction based on mojette transform and compressed sensing, International Journal of Computer and Electrical Engineering, 5(1), 83-87, 2013.
  • Y. Kenmochi, L. Buzer, A. Sugimoto and I. Shimizu, Digital planar surface segmentation using local geometric patterns, Discrete Geometry for Computer Imagery, Springer, 322-333, 2008.
  • D. Khoshnoudirad, Farey lines defining Farey diagrams, and application to some discrete structures, Appl. Anal. Discrete Math., 9(1), 73-84, 2015.
  • A. O. Matveev, A note on Boolean lattices and Farey sequences, Integers, 7, A20, 2007.
  • A. O. Matveev, Relative blocking in posets, J. Comb. Optim., 13(4), 379-403, 2007, Corrigendum: arXiv:math/0411026.
  • A. O. Matveev, Neighboring fractions in Farey subsequences, arXiv:0801.1981, 2008.
  • A. O. Matveev, A note on Boolean lattices and Farey sequences II, Integers, 8, A24, 2008.
  • M. D. McIlroy, A note on discrete representation of lines, AT&T Technical Journal, 64(2), 481-490, 19 E. Remy and E. Thiel, Exact medial axis with euclidean distance, Image and Vision Computing, 23(2), 167-175, 2005.
  • E. Remy and E. Thiel, Structures dans les spheres de chanfrein, RFIA, 483-492, 2000.
  • I. Svalbe and A. Kingston, On correcting the unevenness of angle distributions arising from integer ratios lying in restricted portions of the Farey plane, Combinatorial Image Analysis, Springer, 110- 121, 2005.
  • G. Tenenbaum, Introduction to analytic and probabilistic number theory, 46, Cambridge University Press, 1995.
  • E. Thiel, Les distances de chenfrein en analyse d’images : fondements et applications, Thélse de doctorat, UJF Grenoble, 1994.
  • E. Thiel and A. Montanvert, Chamfer masks: Discrete distance functions, geometrical properties and optimization, Pattern Recognition, Vol. III. Conference C: Image, Speech and Signal Analysis, Proceedings., 11th IAPR International Conference on, IEEE, 244-247, 1992.
  • R. Tomás, Asymptotic behavior of a series of Euler’s totient function ϕ(k) times the index of 1/k in a Farey sequence, arXiv:1406.6991, 2014.
  • R. Tomás, From farey sequences to resonance diagrams, Physical Review Special Topics-Accelerators and Beams, 17(1), 014001, 2014.
  • V. Trifonov, L. Pasqualucci, R. Dalla-Favera and R. Rabadan, Fractal-like distributions over the rational numbers in high-throughput biological and clinical data, Scientific reports, 1, 2011.
  • G. H. Hardy and E. M. Wright, Introduction à la théorie des nombres, Traduction de François Sauvageot, Springer.
Toplam 27 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Bölüm Makaleler
Yazarlar

Daniel Khoshnoudirad Bu kişi benim

Yayımlanma Tarihi 14 Eylül 2015
Yayımlandığı Sayı Yıl 2015 Cilt: 2 Sayı: 3

Kaynak Göster

APA Khoshnoudirad, D. (2015). A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(3), 169-190. https://doi.org/10.13069/jacodesmath.79416
AMA Khoshnoudirad D. A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry. Journal of Algebra Combinatorics Discrete Structures and Applications. Eylül 2015;2(3):169-190. doi:10.13069/jacodesmath.79416
Chicago Khoshnoudirad, Daniel. “A Further Study for the Upper Bound of the Cardinality of Farey Vertices and Application in Discrete Geometry”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, sy. 3 (Eylül 2015): 169-90. https://doi.org/10.13069/jacodesmath.79416.
EndNote Khoshnoudirad D (01 Eylül 2015) A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry. Journal of Algebra Combinatorics Discrete Structures and Applications 2 3 169–190.
IEEE D. Khoshnoudirad, “A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 3, ss. 169–190, 2015, doi: 10.13069/jacodesmath.79416.
ISNAD Khoshnoudirad, Daniel. “A Further Study for the Upper Bound of the Cardinality of Farey Vertices and Application in Discrete Geometry”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/3 (Eylül 2015), 169-190. https://doi.org/10.13069/jacodesmath.79416.
JAMA Khoshnoudirad D. A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:169–190.
MLA Khoshnoudirad, Daniel. “A Further Study for the Upper Bound of the Cardinality of Farey Vertices and Application in Discrete Geometry”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 3, 2015, ss. 169-90, doi:10.13069/jacodesmath.79416.
Vancouver Khoshnoudirad D. A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(3):169-90.