A Space-Efficient Framework for Dynamic Point Location

Abstract. Let G be a planar subdivision with n vertices. A succinct geometric index for G is a data structure that occupies o(n) bits beyond the space required to store the coordinates of the vertices of G, while supporting efficient queries. We describe a general framework for con-verting dynamic data structures for planar point location into succinct geometric indexes, provided that the subdivision G to be maintained has bounded face size. Using this framework, we obtain several succinct geometric indexes for dynamic planar point location on G with query times matching the currently best (non-succinct) data structures and polylogarithmic update times.