Kinetic sorting and kinetic convex hulls

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(nlogn) time), even for linear motions. We also describe a kinetic data structure for so-called gift-wrapping queries on a set S of n moving points in the plane: given a point q and a line l through q such that all points from S lie on the same side of l, report which point piS is hit first when l is rotated around q. Our KDS allows a trade-off between the query time and the maintenance cost: for any Q with 1Qn, we can achieve O(Qlogn) query time with a KDS that processes O(n2+/Q1+1/d) events, where d is the maximum degree of the polynomials describing the motions of the points. This allows us to reconstruct the convex hull quickly when the number of points on the convex hull is small. The structure also allows us to answer extreme-point queries (given a query direction , what is the point from S that is extreme in direction ?) and convex-hull containment queries (given a query point q, is q inside the current convex hull?).