New directions in computational geometry

计算几何的新方向

• 批准号: 228113-2010
• 负责人: Chan, Timothy
• 金额: $ 3.72万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570354
• 关键词: New; directions; computational; geometry

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.

自三十多年前成立以来，计算几何一直是算法设计和分析的一个蓬勃发展的研究领域，在地理信息系统和计算机图形学，计算机辅助制造，统计学和机器人等领域都有许多应用。在这个建议中，我将指出该领域的几个令人兴奋的发展，这些发展使我们能够以新的方式重新思考标准和最基本的问题。