Convex Gridgons

Carleton University

My last seminar talk ended with the following open problem: "Given two sets of real numbers $X$ and $Y$, can we decide in polynomial time if there exists a convex polygon with $x$-coordinates $X$ and $y$-coordinates $Y$?"

While this problem remains open, I will present several related results that were discovered as a result. In particular, I will present tight asymptotic bounds on the largest convex polygon and on the number of convex polygons in these grids.