Jump to content

Dynamic convex hull

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Altenmann (talk | contribs) at 19:01, 1 June 2007 (Created page with '{{inprogress}} The '''dynamic convex hull problem''' is a class of dynamic problem (algorithms)s in computational geometry. The problem consists in the mai...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

 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