New directions in computational geometry

自三十多年前成立以来，计算几何一直是算法设计和分析的一个蓬勃发展的研究领域，在地理信息系统和计算机图形学，计算机辅助制造，统计和机器人等领域有着众多的应用。 在这份提案中，我将指出该领域的几个令人兴奋的发展，使我们能够以新的方式重新思考标准和最基本的问题。 (1)最近，已经表明许多基本几何问题（例如，求直线交点 段）可以令人惊讶地比研究人员以前认为的更快地解决。 的 改进的算法利用字级并行来加速计算，并在“字”下工作 RAM”模型，它在许多方面比传统的“真实的RAM”模型更真实。 (2)传统的算法分析主要集中在最坏情况下的输入，这可能不会经常出现， 实践 最近发现，几个基本的几何问题（例如，计算2-和 三维凸包）承认“实例最优”算法，不仅工作更快，更容易 输入，但可证明在每个输入点集上具有最佳可能的渐近运行时间！ (3)涉及大量数据集的新兴应用程序导致重新审视几何问题， “流”等模式，将重点转向空间使用。 我计划在所有这些不同的设置下找到新的技术和新的算法。 此外，一个总的主题是如何在计算几何和算法设计的其他分支之间的技术连接可以受益于彼此。

Since its inception over thirty years ago, computational geometry has been a thriving field of research in algorithm design and analysis, with numerous applications in areas ranging from geographic information systems and computer graphics, to computer-aided manufacturing, statistics, and robotics. In this proposal, I will identify several exciting developments in the field that allow us to rethink the standard and most fundamental problems in new ways. (1) Recently, it has been shown that many basic geometric problems (e.g., computing intersections of line segments) can surprisingly be solved faster than researchers have previously thought possible. The improved algorithms exploit word-level parallelism to speed up computation and work under the "word RAM" model, which in many ways is more realistic than the traditional "real RAM" model. (2) Traditional algorithm analysis concentrates primarily on worst-case input, which may not arise often in practice. It has recently been discovered that several basic geometric problems (e.g., computing two- and three-dimensional convex hulls) admit "instance-optimal" algorithms that not only work faster on easier input, but has provably the best possible asymptotic running time on every input point set! (3) Emerging applications involving massive data sets have led to a reexamination of geometric problems in models such as "streaming", which turn the focus towards space usage. I plan to find new techniques and new algorithms under all these different settings. In addition, one general theme is how connections between techniques in computational geometry and other branches of algorithm design can benefit from each other.