Gabriel Nivasch
ETH Zürich

We present a "stretched grid", which is a grid of points in R^d in which the distances grow increasingly rapidly in each successive dimension. Convexity in this grid reduces to a nice combinatorial notion which we call "stair-convexity". The stretched grid yields improved bounds for several problems in combinatorial geometry. Joint work with Boris Bukh and Jiri Matousek.

Presentation (PowerPoint File)

Back to Workshop II: Combinatorial Geometry