A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry
Keywords:
Combinatorial number theory, Farey diagrams, Theoretical computer sciences, Discrete planes, Diophantineequations, Arithmetical geometry, Combinatorial geometry, Discrete geometry, Graph theory in computersciencesAbstract
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.
Downloads
References
D. M. Acketa and J. D. Žunić, On the number of linear partitions of the $(m, n)$-grid, Inform. Process. Lett. 38(3) (1991) 163-168.
T. M. Apostol, Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York (1976).
T. Asano and N. Katoh, Variants for the Hough transform for line detection, Comput. Geom. 6(4) (1996) 231-252.
J.-M. Chassery, D. Coeurjolly, and I. Sivignon, Duality and geometry straightness, characterization and envelope, in Discrete Geometry for Computer Imagery (DGCI 2006), Lecture Notes in Comput. Sci. 4245, Springer, Berlin (2006) 1-16.
J.-M. Chassery and A. Montanvert, Geometrical representation of shapes and objects for visual perception, in Geometric Reasoning for Perception and Action, Lecture Notes in Comput. Sci. 708, Springer, Berlin (1993) 163-182.
A. Daurat, M. Tajine, and M. Zouaoui, About the frequencies of some patterns in digital planes: Application to area estimators, Comput. & Graphics 33(1) (2009) 11-20.
I. Debled-Rennesson, Étude et reconnaissance des droites et plans discrets, Thèse de doctorat, Université Louis Pasteur, Strasbourg (1995).
E. Domenjoud, D. Jamet, D. Vergnaud, and L. Vuillon, Enumeration formula for $(2, n)$-cubes in discrete planes, Discrete Appl. Math. 160(15) (2012) 2158-2171.
E. Szemerédi and W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica 3(3-4) (1983) 381-392.
A. Hatcher, Topology of Numbers, Unpublished manuscript, in preparation (2015).
P. Haukkanen and J. K. Merikoski, Asymptotics of the number of threshold functions on a two-dimensional rectangular grid, Discrete Appl. Math. 161(1-2) (2013) 13-18.
W. Hou and C. Zhang, Parallel-beam CT reconstruction based on Mojette transform and compressed sensing, Int. J. Comput. Electr. Eng. 5(1) (2013) 83-87.
Y. Kenmochi, L. Buzer, A. Sugimoto, and I. Shimizu, Digital planar surface segmentation using local geometric patterns, in Discrete Geometry for Computer Imagery (DGCI 2008), Lecture Notes in Comput. Sci. 4992, Springer, Berlin (2008) 322-333.
D. Khoshnoudirad, Farey lines defining Farey diagrams, and application to some discrete structures, Appl. Anal. Discrete Math. 9(1) (2015) 73-84.
A. O. Matveev, A note on Boolean lattices and Farey sequences, Integers 7 (2007) #A20.
A. O. Matveev, Relative blocking in posets, J. Comb. Optim. 13(4) (2007) 379-403.
A. O. Matveev, Neighboring fractions in Farey subsequences, arXiv:0801.1981 [math.CO] (2008).
A. O. Matveev, A note on Boolean lattices and Farey sequences II, Integers 8 (2008) #A24.
M. D. McIlroy, A note on discrete representation of lines, AT&T Tech. J. 64(2) (1985) 481-490.
E. Remy and E. Thiel, Exact medial axis with euclidean distance, Image Vision Comput. 23(2) (2005) 167-175.
E. Remy and E. Thiel, Structures dans les sphères de chanfrein, in 12e Congrès de Reconnaissance des Formes et Intelligence Artificielle (RFIA 2000), Paris (2000) 483-492.
I. Svalbe and A. Kingston, On correcting the unevenness of angle distributions arising from integer ratios lying in restricted portions of the Farey plane, in Combinatorial Image Analysis (IWCIA 2004), Lecture Notes in Comput. Sci. 3322, Springer, Berlin (2004) 110-121.
G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Graduate Studies in Mathematics 163, American Mathematical Society, Providence, RI (2015).
E. Thiel, Les distances de chanfrein en analyse d'images : fondements et applications, Thèse de doctorat, Université Joseph Fourier, Grenoble (1994).
E. Thiel and A. Montanvert, Chamfer masks: Discrete distance functions, geometrical properties and optimization, in Proceedings of 11th IAPR International Conference on Pattern Recognition, Vol. III, IEEE (1992) 244-247.
R. Tomás, Asymptotic behavior of a series of Euler's totient function $\phi(k)$ times the index of $1/k$ in a Farey sequence, ScienceOpen Research (2014) arXiv:1406.6991.
R. Tomás, From Farey sequences to resonance diagrams, Phys. Rev. ST Accel. Beams 17(1) (2014) 014001.
V. Trifonov, L. Pasqualucci, R. Dalla-Favera, and R. Rabadan, Fractal-like distributions over the rational numbers in high-throughput biological and clinical data, Sci. Rep. 1 (2011) 191.
G. H. Hardy and E. M. Wright, Introduction à la théorie des nombres, Traduction de François Sauvageot, Vuibert-Springer, Paris (2007).
