Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949149 | Computational Geometry | 2017 | 9 Pages |
Abstract
A finite set of real numbers is called convex if the differences between consecutive elements form a strictly increasing sequence. We show that, for any pair of convex sets A,BâR, each of size n1/2, the convex grid AÃB spans at most O(n37/17log2/17â¡n) unit-area triangles. Our analysis also applies to more general families of sets A, B, known as sets of Szemerédi-Trotter type.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Orit E. Raz, Micha Sharir, Ilya D. Shkredov,