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.

Timothy Chan, University of Waterloo, Canada

 

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube