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

University Of California-Irvine, Irvine CA

Investigators

Abstract

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.