The Diagonal's Problem - ISISS M. Casagrande (Pieve di Soligo)

This paper investigates the grid-intersection problem within a discrete geometric framework, extending the classic analysis of a straight diagonal to a parabolic curve. Given a rectangle of dimensions b x h divided into b x h unit squares, we determine the number of squares n intersected by the path and the number of grid vertices i lying strictly inside it. First, we analyze the diagonal case, providing an original geometric proof using Pick's Theorem and Manhattan
geometry, complemented by algorithmic optimizations to nd the intersections. Second, we generalize the problem to a parabolic arc with a more algebraic approach. By leveraging prime factorization and the ceiling function, we derive an expression to compute the internal vertices and establish precise conditions and numerical bounds for their existence.