Computational geometry for non-geometers: recent developments on some classical problems

In this talk, I will discuss some "textbook exercises" in low-dimensional computational geometry that any algorithmist with no computational-geometry background can attempt to solve: Given a set of red and blue points, is there a red point dominating (bigger along all coordinates than) a blue point? Given a set of horizontal and vertical line segments, is there an intersection? Given a set of axis-parallel boxes, is there a box strictly contained in another box? There are connections to non-geometric problems such as counting inversions and all-pairs shortest paths. Remarkably, certain versions of these problems are still open! I will describe the latest worst-case results in the standard word-RAM model, as well as the recent surprising discovery of "instance-optimal" algorithms in the traditional comparison model.