Description
We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of $n$ real numbers. We prove that every such grid contains a convex polygon with $\Omega(\log n)$ vertices and that this bound is tight up to a constant factor. We generalize this result to $d$ dimensions (for a fixed $d$), and obtain a tight lower bound of $\Omega(\log^{d-1}n)$ for the maximum number of points in convex position in a $d$-dimensional grid. We also present exponential upper and lower bounds on the maximum number of convex polygons in planar grids.These bounds are tight up to polynomial factors. (Joint work with Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, and Sander Verdonschot.)