Yakov Nekrich, associate professor of Computer Science, is the principal investigator of a new three-year, $594,059 National Science Foundation (NSF) grant titled, “AF:Small: Fundamental Geometric Data Structures.” The project will study geometric data structures and their connections with other areas of theoretical computer science.
An NSF Computer and Information Science and Engineering Core Program, the Algorithmic Foundations (AF) award supports research on the theory of algorithms focused on problems that are central to computer science and engineering, and the development of new algorithms and techniques for analyzing algorithms and computational complexity.
Nekrich’s areas of expertise include string algorithms, compressed data structures, and computational geometry. Visit his faculty website. Nekrich is a member of the Institute of Computing and Cybersystems’s (ICC) Center for Scalable Architectures and Systems (SAS). View his publications on Google Scholar.
Nekrich is seeking motivated students interested in algorithms and data structures.
Project Abstract
Efficient methods of storing and querying large data volumes play a crucial role in a majority of computer applications. In many situations both the stored data and the queries can be represented as geometric objects, such as points, lines, and rectangles. This scenario is traditionally studied in computational geometry. However geometric data structures have numerous applications in other areas of Computer Science, from spatial databases to geographic information systems, from computer graphics to bioinformatics. This project will study geometric data structures and their connections with other areas of theoretical Computer Science. The project will also study the implementations of obtained algorithms and their potential applications.
This project will focus on fundamental geometric data structuring problems: the orthogonal range searching problem, the point location problem, the nearest neighbor problem, and the dynamic convex hull problem. Despite several decades of extensive study, there is still a number of important open questions related to these problems.
The purpose of this project is to extend and deepen the knowledge of this area: reduce or eliminate the gaps between the lower and upper bounds, investigate the relative complexities of problems in different models of computation, and find more efficient ways to dynamize the static data structures. The project will also explore the connections between geometric data structures and algorithms in the external memory model.