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:
“Imagination is always the fabric of social life and the dynamic of history. The influence of real needs and compulsions, of real interests and materials, is indirect because the crowd is never conscious of it.”
—Simone Weil (1909–1943)
“Most childhood problems don’t result from “bad” parenting, but are the inevitable result of the growing that parents and children do together. The point isn’t to head off these problems or find ways around them, but rather to work through them together and in doing so to develop a relationship of mutual trust to rely on when the next problem comes along.”
—Fred Rogers (20th century)