Convex Polygons in Cartesian Products

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of $n$ real numbers (for short, \emph{grid}). First, we prove that every such grid contains $Ω(\log n)$ points in convex position and that this bound is tight up to a constant factor. We generalize this result to $d$ dimensions (for a fixed $d\in \mathbb{N}$), and obtain a tight lower bound of $Ω(\log^{d-1}n)$ for the maximum number of points in convex position in a $d$-dimensional grid. Se...