Editing Computational geometry (section)

==== Dynamic problems ====

Yet another major class is the [[dynamic problem (algorithms)|dynamic problem]]s, in which the goal is to find an efficient algorithm for finding a solution repeatedly after each incremental modification of the input data (addition or deletion input geometric elements). Algorithms for problems of this type typically involve [[dynamic data structures]]. Any of the computational geometric problems may be converted into a dynamic one, at the cost of increased processing time. For example, the [[range searching]] problem may be converted into the [[dynamic range searching]] problem by providing for addition and/or deletion of the points. The [[dynamic convex hull]] problem is to keep track of the convex hull, e.g., for the dynamically changing set of points, i.e., while the input points are inserted or deleted.

The computational complexity for this class of problems is estimated by:
* the time and space required to construct the data structure to be searched in
* the time and space to modify the searched data structure after an incremental change in the search space
* the time (and sometimes an extra space) to answer a query.