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

Year 2015, , 169 - 190, 14.09.2015

Daniel Khoshnoudirad

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.

Keywords

Combinatorial number theory, Farey diagrams, Theoretical computer sciences, Discrete planes, Diophantineequations, Arithmetical geometry, Combinatorial geometry, Discrete geometry, Graph theory in computersciences

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.