Speaker:Yakov Nekrich

Data Structures for Computational Geometry

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, a set of points P is stored in a data structure 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 for these fundamental geometric problems and describe some recent results.

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.  
Dr. Nekrich has authored around 100  conference and journal papers, including publications in  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.