NSF-BSF: AF: Small: Geometric Realizations and Evolving Data

该项目涉及几何实现和演化数据的综合研究。几何实现是实现组合约束和几何约束的关系的结构，演进数据捕获数据随时间变化的方式。特别感兴趣的是几何实现和社会中不断发展的数据应用所带来的算法挑战，包括物理、数据可视化和快速变化数据的在线服务。该项目的一个重要组成部分是让学生参与研究；因此，这项计划有可能为培养下一代资讯科技研究人员带来更多的教育和研究机会。此外，该项目涉及美国和以色列研究人员之间的合作，预计将促进这两个国家之间的进一步联系。*稳定匹配Voronoi图，它是通过结合由涉及给定点集的距离决定的几何约束和基于这些点之间匹配偏好的组合约束来确定的平面细分。*多多边形，在正交晶格中连接的细胞。这些通常用于模拟物理中的渗透网络。*几何图形，用点表示顶点，用直线表示边。*响应式数据结构，这是一种有效的数据表示，支持数据启用和禁用操作以及查询。*近似表示，这是一种数据配置，为数据集提供良好的近似解，这些数据集以与算法速度相称的速率变化。对于这些和相关的主题，研究的目标是开发快速有效的算法和数据结构，基于利用图形绘制，计算几何和计算理论的方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project involves an integrated study of geometric realizations and evolving data. Geometric realizations are structures that realize relationships combining combinatorial and geometric constraints, and evolving data captures ways in which data changes over time. Of particular interest are algorithmic challenges arising from geometric realizations and evolving data applications in society, including physics, data visualization, and on-line servicing of fast-changing data. A vital component of the project involves the involvement of students in research; hence, this project has the potential of bringing expanded educational and research opportunities for developing the next generation of information technology researchers. In addition, this project involves a collaboration between researchers in the United States and Israel, which is expected to foster further ties between these two countries.Specific topics of interest in this project include the following:* Stable-matching Voronoi diagrams, which are planar subdivisions determined by combining geometric constraints determined by distances involving a given set of points and combinatorial constraints based on matching preferences among these points.* Polyominoes, which are connected cells in an orthogonal lattice. These are often used to model percolation networks in physics.* Geometric graphs, which are representations of graphs using points for vertices and straight lines for edges.* Reactive data structures, which are efficient data representations that support data enable and disable operations along with queries.* Approximate representations, which are data configurations that provide good approximate solutions for data sets that are changing at a rate commensurate with the speed of the algorithm. For each of these and related topics, the goal of the research is to develop fast and efficient algorithms and data structures, based on exploiting methods from graph drawing, computational geometry, and theory of computation.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.