Lower Bounds for Kinetic Sorting
Mohammad Ali Abam, Mark de Berg · TU/e Research Portal · 2005
Let S be a set of n points moving on the real line. The kinetic sorting problem is to maintain a data structure on the set S that makes it possible to quickly generate a sorted list of the points in S, at any given time. We prove tight lower bounds for this problem, which show the following: with a subquadratic maintenance cost one cannot obtain any significant speed-up on the time needed to generate the sorted list (compared to the trivial O(n log n) time), even for linear motions.