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.
Although the convex hull of a set of points in the plane may incur a linear amount of change when a single point is inserted or deleted, there are data structures that can maintain searchable representations of the hull in an amount of time per update that is much smaller than linear. For many years the best algorithm of this type was that of Overmars and van Leeuwen (1981), which took time O(log2 n) per update, but it has since been improved by Timothy M. Chan and others.
References
- Overmars, M. H.; van Leeuwen, J. (1981). "Maintenance of configurations in the plane". J. Comput. Sys. Sci. 23 (2): 166–204. doi:10.1016/0022-0000(81)90012-X.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Jacob Rico, Dynamic Planar Convex Hull (2002), a BRICS dissertation