2026-07-22T06:37:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24938 2026-02-09T08:02:19Z ddc:004 open_access

Incidences Between Curves and Points on the Grid Ezra, Esther Sharir, Micha Geometric incidences uniform grid bounded spread Pick’s theorem range searching We derive an improved upper bound for the number of incidences between the n vertices of a uniform grid and m convex or concave curves, each pair of which intersect in at most s points, for some integer parameter s ≥ 1. For a square grid, our bound is O(n^{2/3}m^{2/3} + m^{1-1/(3s)} n^{(s+1)/3s} + m + n) . This improves a general bound of O(m n^{1/3}) on the number of incidences with respect to vertices of a grid and convex or concave curves. For a rectangular grid, which fits inside a 1×K rectangle, for some integer K > 1 (which generally may depend on n), the bound also depends on how large K is. The precise result is stated in Theorem 2, but, roughly, we get the same bound as above when K is not too large. Our analysis competes with a celebrated result of Bombieri and Pila [E. Bombieri and J. Pila, 1989], which gives (usually) a sharper bound if we assume that the input curves are algebraic of constant degree and the input points are vertices of the square grid. However, the analysis in [E. Bombieri and J. Pila, 1989] strongly relies on these assumptions, and cannot be extended to handle the more general setup considered here. As a main application, of independent interest, we present a variant of our technique for semi-algebraic range reporting on sets of points of "bounded spread" in the plane. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esther Ezra and Micha Sharir 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.30 urn:nbn:de:0030-drops-249387 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.30 eng https://creativecommons.org/licenses/by/4.0/legalcode