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:
“We Americans have the chance to become someday a nation in which all radical stocks and classes can exist in their own selfhoods, but meet on a basis of respect and equality and live together, socially, economically, and politically. We can become a dynamic equilibrium, a harmony of many different elements, in which the whole will be greater than all its parts and greater than any society the world has seen before. It can still happen.”
—Shirley Chisholm (b. 1924)
“Every child is an artist. The problem is how to remain an artist once he grows up.”
—Pablo Picasso (1881–1973)