Presidential Young Investigator: Randomized Geometric Algorithms and Data Structures

这个项目研究了在涉及大量对象的几何问题的算法和数据结构设计中使用随机化的可能性，特别强调了所谓的高维点问题的各个方面。目标是设计允许在d空间的多面体分区中快速定位查询点的数据结构。研究了在处理时间、空间占用、查询时间等方面可能存在的各种范围查询问题。

This project investigates the possible use of randomization in the design of algorithms and data structures for geometric problems that involve a large number of objects, with a particular emphasis various aspects of the so-called higher-dimensional point problem. The goal is to design data structures that permit the rapid location of a query point in a polyhedral partition of d- space. Various range query problems which consider possible between preprocessing time, space usage, query time, and are also investigated.