Planar Convex Hull Maintenance with Kinetic Heaps
Let a convex set in the plane be given by either a set of points or half-spaces. The maintenance of it under insertion and deletion of elements is a fundamental problem in computational geometry. This thesis considers a data-structure which solves this problem. It was drafted by the researchers Kaplan, Tarjan and Tsioutsiouliklis in a paper about kinetic heaps (priority queues with linear functions as keys rather than fixed values). However it was never written down in detail. We state their construction explicitly. Its foundation is built by a deletion-only structure which uses finger trees (height balanced trees with preferred access points) to represent convex sets. With the semi-dynamic structure at hand, a fully dynamic one may be constructed using given dynamization transformations. The binary counting scheme transformation of Bentley and Saxe yields an insertion-and-deletion structure with O(log2 n) worst-case vertical ray query time, O(log n) amortized insertion time and O(log n log log n) amortized deletion time. A transformation of Brodal and Jacob results in a structure with O(log n) worst-case vertical ray query time, O(log n log log log n) amortized insertion and O(log n log log n) amortized deletion time.