Kinetic sorting and kinetic convex hulls
The main result of the paper is determining tight lower bounds for the problem of kinetic sorting (which means: to maintain a data structure on the real set \(S\) of \(n\) points moving on the real line so to be able to quickly generate a sorted list of the points in \(S\) at any given time). Some other results concerning kinetic data structure are also given.
scientific article; zbMATH DE number 5134246