Computational Geometry for Non-Geometers:Recent Developments on Some Classical Problems

22nd Annual ACM-SIAM Symposium on Discrete Algorithms

数学;计算机科学

Timothy Chan

Others  :  http://www.siam.org/proceedings/soda/2011/SODA11_109_chant.pdf
PID  :  27446

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

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.