CS Colloquium Lecture: Yakov Nekrich, Computer Science


Associate Professor Yakov Nekrich, Computer Science, will present a Department of Computer Science Colloquium lecture on Friday, March 17, 2023, from 3-4 p.m., in Rekhi Hall Room 214 and virtually.

Nekrich works on efficient algorithms for geometric and sequence data. He is especially interested in space-efficient and compressed data structures and their applications to the world of big data. The title of his talk is, “Geometric Data Structures: Point Location and Range Reporting.”

View the lecture slides below.

Talk Title: Geometric Data Structures: Point Location and Range Reporting

Talk Abstract: In this talk we give an overview of some recent results in geometric data structures. We consider two fundamental problems, the orthogonal range reporting and the dynamic point location problem. In the range reporting problem, we keep a set of points P so that for any axis-parallel query rectangle Q all points from P\cap Q can be reported efficiently. In the two-dimensional point location problem, we store a planar sub-division so that for any query point q the polygon containing q can be found efficiently. In this talk we review the state of the art in these fundamental geometric problems and describe several recent results.

Speaker Biography: Yakov Nekrich is an associate professor at Michigan Technological University. He works on efficient algorithms for geometric and sequence data. He is especially interested in space-efficient and compressed data structures and their applications to the world of big data.

Nekrich has authored about 100 conference and journal papers, including such venues as SIAM Journal of Computing, IEEE/ACM Transactions on Bioinformatics and Computational Biology, ACM Symposium on Discrete Algorithms, ACM Transactions on Database Systems and IEEE Symposium on Foundations of Computer Science.

He has held visiting research professor position at the University of Paris Est, France, and served on program committees of several major conferences, including SoCG, PODS, ICDT, and ICDE.