Using Bistellar Flips for Rotations in Point Location Structures
Benoît Hudson, Gary Lee Miller · Canadian Conference on Computational Geometry · 2004
Point location in dynamic Delaunay triangulations is a problem that as yet has no elegant solution. Current approaches either only give guarantees against a weakened adversary, or require superlinear space. In this paper we propose that we should seek intuition from balanced binary search trees, where rotations are used to maintain a shallow worst-case depth. We describe a (well-known) data structure and a novel and simple algorithm based on bistellar flips to implement rotation in the structure. The rotation takes time linear in the change in the data structure. The hope is to provide a tool that would lead to the design of an efficient dynamic Delaunay point location data structure.