Geometric Data Structures: A 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.