New directions in computational geometry

自三十多年前诞生以来，计算几何一直是算法设计和分析领域的一个蓬勃发展的研究领域，在从地理信息系统和计算机图形学到计算机辅助制造、统计和机器人等领域有着广泛的应用。在这项提案中，我将确定该领域的几个令人振奋的发展，使我们能够以新的方式重新思考标准和最根本的问题。 (1)最近，已经证明了许多基本的几何问题(例如，计算直线的交点 片段)可以出人意料地比研究人员之前认为的可能的速度更快地被解决。这个 改进的算法利用字级并行来加快计算速度，并在“Word”下工作 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.