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 n edges. Our data structure uses O ( n ) space, answers queries in O (log n ) time, and supports updates in O (log n ) time. Our solution is based on a data structure for vertical ray shooting queries that supports queries and updates in O (log n ) time.

Authors

• Yakov Nekrich

Keywords

• dynamic data structures
• computational geometry
• point location