Dynamic planar point location in optimal time

In this paper we describe a fully-dynamic data structure that supports point location queries in a connected planar subdivision with 𝑛 edges. Our data structure uses 𝑂 (𝑛) space, answers queries in 𝑂 (log 𝑛) time, and supports updates in 𝑂 (log 𝑛) time. Our solution is based on a data structure for vertical ray shooting queries that supports queries and updates in 𝑂 (log 𝑛) time.