Practical Insertion-Only Convex Hull

Convex hull data structures are fundamental in computational geometry. We study insertiononly data structures for convex hulls of a planar point set \(P\) of size \(n\), supporting various containment and intersection queries. When \(P\) is sorted by \(x\)- or \(y\)-coordinate, convex hulls can be constructed in linear time using classical algorithms such as Graham scan. In the fully dynamic setting, the algorithm by Overmars and van Leeuwen [35] maintains the convex hull under insertions and deletions in \(O(\text{log}^2 n)\) time per update, supports queries in time logarithmic in the size of the convex hull, and uses \(O(n)\) space. An open-source implementation of their method is available.