Dynamic Closest-pair Problem
The dynamic version for the closest-pair problem is stated as follows:
- Given a dynamic set of objects, find algorithms and data structures for efficient recalculation of the closest pair of objects each time the objects are inserted or deleted.
If the bounding box for all points is known in advance and the constant-time floor function is available, then the expected O(n) space data structure was suggested that supports expected-time O(log n) insertions and deletions and constant query time. When modified for the algebraic decision tree model, insertions and deletions would require O(log2 n) expected time. It is worth noting, though, that the complexity of the dynamic closest pair algorithm cited above is exponential in the dimension d, and therefore such an algorithm becomes less suitable for high-dimensional problems.
Read more about this topic: Closest Pair Of Points Problem
Famous quotes containing the words dynamic and/or problem:
“Knowledge about life is one thing; effective occupation of a place in life, with its dynamic currents passing through your being, is another.”
—William James (1842–1910)
“In the nineteenth century the problem was that God is dead; in the twentieth century the problem is that man is dead.”
—Erich Fromm (1900–1980)