Many algorithms to compute convex hulls or envelopes are static and cannot be extended to work dynamically, that is, to support changes like insertions or deletions in the data set. Overmars and van Leeuwen proposed a data structure that allows this for both convex hulls and envelopes. The data structure is a binary search tree where elements are stored in the leafs and the internal nodes are augmented with another data structure to store the convex hull or envelope. Recently a new algorithm was developed to maintain the lower envelope of pseudo-lines by Agarwal et al. which is based on the Overmars and van Leeuwen data structures.

While dynamic convex hulls have been studied extensively from a theoretical perspective, there is only very little experimental work. In this work we evaluate the practicability of the Overmars and van Leeuwen data structure and its extension by Agarwal et al.

We implemented and compared several versions of the data structure by Overmars and van Leeuwen and compared it to a simple approach based on maintaining the Delaunay triangulation. In our experiments, Delaunay triangulations outperformed the dedicated data structures except for very large sizes of convex hulls.

We also implemented the data structure for maintaining the lower envelope of pseudo-lines by Agarwal et al. The algorithm performs as expected, but our implementation suffers from robustness issues.