Geometric Data Structures: A Modern Perspective

几何数据结构：现代视角

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

Although data structures in computational geometry have been studied for over four decades, recent years have seen groundbreaking new developments for some of its most fundamental problems, including (orthogonal and nonorthogonal) range searching, (approximate) nearest neighbor search, (dynamic) point location, and more. In this proposal, I plan to not only continue studying the fundamental problems of the area, but also investigate new problems arising from modern needs. For example: * Today's world of "big data" makes space-efficient geometric data structures all the more important, in both traditional computational models as well as emerging data streaming and sketching models. * Various modern-day applications require extending standard geometric data structure problems to different settings (e.g., time-windowed, kinetic, or high-dimensional), or introducing variations on old problems (e.g., range-aggregate queries), all leading to interesting new challenges. * There have been some surprising recent applications of geometric data structures to non-geometric problems, on strings and text indexing; it will be exciting to find further connections between computational geometry and other areas of algorithms. The proposal is expected to produce not only new algorithms for specific problems but also new general techniques and deeper understanding of geometric data structures.

虽然计算几何中的数据结构已经研究了四十多年，但近年来在一些最基本的问题上出现了突破性的新发展，包括（正交和非正交）范围搜索，（近似）最近邻搜索，（动态）点定位等。在这个建议中，我计划不仅继续研究该地区的基本问题，而且还调查现代需求所产生的新问题。举例来说： * 当今的“大数据”世界使得节省空间的几何数据结构变得更加重要，无论是在传统的计算模型中，还是在新兴的数据流和草图模型中。 * 各种现代应用需要将标准几何数据结构问题扩展到不同的设置（例如，时间窗的、动力学的或高维的），或引入旧问题的变化（例如，范围聚合查询），所有这些都带来了有趣的新挑战。 * 最近有一些令人惊讶的几何数据结构应用于非几何问题，字符串和文本索引;这将是令人兴奋的，以找到计算几何和其他领域的算法之间的进一步联系。 该建议预计不仅产生新的算法，为特定的问题，但也有新的一般技术和更深入的理解几何数据结构。