BibTex RIS Cite

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

Year 2015, Volume: 2 Issue: 3, 169 - 190, 14.09.2015
https://doi.org/10.13069/jacodesmath.79416

Abstract

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.

References

  • 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.
Year 2015, Volume: 2 Issue: 3, 169 - 190, 14.09.2015
https://doi.org/10.13069/jacodesmath.79416

Abstract

References

  • 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.
There are 27 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

Daniel Khoshnoudirad This is me

Publication Date September 14, 2015
Published in Issue Year 2015 Volume: 2 Issue: 3

Cite

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. September 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, no. 3 (September 2015): 169-90. https://doi.org/10.13069/jacodesmath.79416.
EndNote Khoshnoudirad D (September 1, 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, vol. 2, no. 3, pp. 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 (September 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, vol. 2, no. 3, 2015, pp. 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.