Yakov Nekrich
Home Publications Research Teaching Contact

Point Location



Point Location
In the planar point location problem we store a polygonal subdivision of the plane in a data structure. For any query point q we must be able to find the polygon (also called the face) that contains q. The static data structure for this problem uses linear space and answers queries in O(log n) time. In the dynamic variant of this problem we must also support insertions and deletions of edges. Existence of a dynamic data structure with logarithmic time for both queries and updates has been an open question for several decades. A data structure with close to optimal trade-offs for this problem was constructed in 2015 (see Chan and Nekrich, SIAM J. Comp. 2018). Recently, this problem was completely resolved: there is a data structure that supports point location queries, insertions, and deletions in O(log n) time (see Nekrich, STOC 2021). A number of variants of the point location problem have also been studied extensively. Researchers considered e.g., point location in three dimensions, adaptive data structures, the case when the subdivision is not connected, and point location in the external memory model.

Publications



Orthogonal Range Searching

Photo
In this problem we keep a set of multi-dimensional points P in a data structure, so that for any axis-parallel query rectangle Q some information about points from P ∩ Q can be computed efficiently. Some frequently considered variants are range reporting (report the list of all points in P ∩ Q), range counting (compute the number of points in P ∩ Q), and range maxima (find the point with the highest priority in P ∩ Q). In addition to computational geometry, range searching is used in string algorithms and database theory.

Publications



Compressed Data Structures

Compressed data structures is a thriving research area at the intersection of data structures and data compression. The goal is to represent the data in the most compact way possible so that these data can be queried efficiently. The study of compressed data structures is motivated by the constantly growing volumes of data that must be stored and processed and by situations when the storage capacity is limited. Compressed data structures are interesting in their own right and as a part of algorithms that work on compressed data without decompressing it. Compressed data structures also find numerous applications in other areas, e.g., they are used to reduce the space consumption of geometric data structures. Although this area has been extensively studied for over two decades, there is still a number of important open questions.

Publications