Geometric Data Structures

建议：CCF-0830734标题：几何数据结构PI：Souvan，Diane L.机构：塔夫茨大学几何数据结构摘要数据结构是信息的储存库；目标是组织数据，使其需要较少的存储(空间)，从而可以快速检索(查询)信息。几何数据结构处理具有附加位置的数据(例如，马萨诸塞州消防站的地址)。几何数据结构已经变得无处不在，成为生活中不可或缺的一部分；可以通过查询来生成行驶方向或最近的意大利餐厅的名称。由于数据结构的空间和查询时间取决于它必须支持的查询类型，因此研究哪些工具和技术适用于哪些数据结构非常重要。对更好的数据结构的不断追求有时会导致方法的改进，有时会导致全新的技术。这个研究项目致力于为几何查询和几何决策问题创建新的、高效的数据结构，缩小已知的上下界之间的差距。具体问题包括平面单纯形空查询、动态细分中的相对凸壳查询和动态垂直射线射击查询，以及所得到的数据结构在真实RAM和字RAM模型中的实现。该项目还解决了计算几何中的关键问题，如计算低交叉数的生成树，构造三维空间中的最小尺寸切割，以及从不相交的线段生成凸细分，以解决平面重构问题，如相容几何匹配问题。这些问题的解决将有助于为几何查询创建高效的数据结构，如多点定位、射线拍摄和范围搜索。这些数据结构是计算几何领域的基础，在计算机图形学、机器人学、CAD/CAM、运动规划、碰撞检测和地理信息系统中有着广泛的应用。

Proposal: CCF- 0830734Title: Geometric Data StructuresPI: Souvaine, Diane L.Institution: Tufts UniversityGeometric Data StructuresAbstractA data structure is a repository of information; the goal is to organize the data so that it needs less storage (space) and so that information can be retrieved quickly (query). A geometric data structure handles data which has locations attached to it (e.g. addresses of fire stations in the state of Massachusetts). Geometric data structures have become pervasive and an integral part of life; and can be queried to produce driving directions or the name of the nearest Italian restaurant. Since the space and query time of a data structure depend upon the type of queries it has to support, it is important to study which tools and techniques are suitable for which data structures. The ongoing quest for better data structures sometimes results in improved methods and sometimes results in entirely new techniques. The goal is to determine optimal data structures with the best possible performance.This research project focuses on creating new and efficient data structures for geometric queries and geometric decision problems that close the gaps between known lower and upper bounds. Particular problems include planar simplex emptiness queries, relative convex hull queries in dynamic subdivisions, and dynamic vertical ray shooting queries, and the implementation of the resulting data structures in both the real RAM and word RAM models. The project also addresses key problems in computational geometry such as computing spanning trees with low crossing number, constructing minimum size cuttings in 3-space, and generating convex subdivisions from disjoint line segments in such a way as to solve plane reconfiguration problems such as the compatible geometric matching problem. Solutions to these problems will contribute to the creation of efficient data structures for geometric queries such as multi-point location, ray shooting, and range searching. These data structures are fundamental to the field of computational geometry, and have broad applications in computer graphics, robotics, CAD/CAM, motion planning, collision detection, and geographic information systems.