Dynamic convex hull
In progress
The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for the dynamically changing input data, i.e., when input data elements may be inesrted, deleted, or modified. Problems of this class may be distinguished by the types of the input data and the allowed types of modification of the input data.
Set of points
The convex hull for a set of N points is a basic problem in computational geometry with a variety of algorithms known.
It is easy to construct an example for which the convex hull contains all input points, but after the insertion of a single point the convex hull becomes a triangle. And conversely, the deletion of a single point may produce the opposite drastic change of the size of the output. Therefore without further restrictions the lower bound for the worst-case computational complexity of the recomputation of the convex hull is . This lower bound is attainable, because several general-purpose convex hull algorithms run in linear time when input points are ordered in some way and logarithmic-time methods for dynamic maintenance of ordered data are well-known.
References
- Jacob Rico, Dynamic Planar Convex Hull (2002), a BRICS dissertation