The paper, “Optimal-Time Dynamic Planar Point Location in Connected Subdivisions,” describes an optimal-time solution for the dynamic point location problem and answers an open problem in computational geometry.
The data structure described in the paper supports queries and updates in logarithmic time. This result is optimal in some models of computation. Nekrich is the sole author of the publication.
The annual ACM Symposium on Theory of Computing (STOC), is the flagship
conference of SIGACT, the Special Interest Group on Algorithms and
Computation Theory, a special interest group of the Association for
Computing Machinery (ACM).