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

NSF-BSF：AF：小型：几何实现和不断变化的数据

基本信息

批准号：
1815073
负责人：
Michael Goodrich
金额：
$ 47.44万
依托单位：
University of California-Irvine
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815073&HistoricalAwards=false
关键词：
NSF BSF AF Small Geometric

项目摘要

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.

该项目涉及几何实现和不断发展的数据的综合研究。几何实现是实现结合组合和几何约束的关系的结构，并且不断发展的数据捕获了数据随时间变化的方式。特别令人感兴趣的是由于几何实现和社会中的数据应用所带来的算法挑战，包括物理学，数据可视化和快速变化数据的在线服务。该项目的重要组成部分涉及学生参与研究；因此，该项目有潜力为发展下一代信息技术研究人员带来扩大的教育和研究机会。此外，该项目还涉及美国和以色列研究人员之间的合作，预计这两个国家之间将进一步联系。该项目的特定主题包括以下内容：*稳定匹配的voronoi图，这是通过涉及涉及给定的点数和组合物的较大范围来确定的差异来确定的差异来确定的，这些分量是基于这些定位的较差的测定物，这些差异是基于这些定点的构图，并构成了构图的构图。构成的构图。在正交晶格中连接的细胞。这些通常用于建模物理学中的渗透网络。对于这些和相关的主题，该研究的目的是基于图形图，计算几何学和计算理论的利用方法来开发快速有效的算法和数据结构。该奖项反映了NSF的法定任务，并通过该基金会的智力功能和广泛的影响来评估NSF的法定任务，并被视为值得通过评估的支持。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Stable-matching Voronoi diagrams: Combinatorial complexity and algorithms

稳定匹配 Voronoi 图：组合复杂度和算法

DOI：
10.20382/jocg.v11i1a2
发表时间：
2020
期刊：
Journal of computational geometry
影响因子：
0.3
作者：
Gill Barequet, David Eppstein
通讯作者：
Gill Barequet, David Eppstein

Exact Learning of Multitrees and Almost-Trees Using Path Queries

DOI：
10.48550/arxiv.2208.04216
发表时间：
2022-08
期刊：
影响因子：
0
作者：
Ramtin Afshar;M. Goodrich
通讯作者：
Ramtin Afshar;M. Goodrich

Reconstructing Biological and Digital Phylogenetic Trees in Parallel

并行重建生物和数字系统发育树

DOI：
10.4230/lipics.esa.2020.3
发表时间：
2020
期刊：
ESA
影响因子：
0
作者：
Ramtin Afshar, Michael T.
通讯作者：
Ramtin Afshar, Michael T.

Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model

分叉中的原子力：在非原子二元分叉连接模型中实现蝴蝶网络的超对数下界

DOI：
10.1137/1.9781611976465.128
发表时间：
2021
期刊：
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Goodrich, Michael T;Jacob, Riko;Sithinava, Nodari
通讯作者：
Sithinava, Nodari

Diamonds are Forever in the Blockchain: Geometric Polyhedral Point-Set Pattern Matching

钻石在区块链中永远存在：几何多面体点集模式匹配

DOI：
发表时间：
2022
期刊：
Canadian Conference on Computational Geometry
影响因子：
0
作者：
Barequet, Gill;Fukuzawa, Shion;Goodrich, Michael;Mount, David;Osegueda, Martha;Ozel, Evrim
通讯作者：
Ozel, Evrim