Lower bounds for kinetic sorting

M.A. Abam, M. Berg, de

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Abstract

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.
Original languageEnglish
Title of host publicationAbstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)
EditorsM.T. Berg, de
PublisherTechnische Universiteit Eindhoven
Pages171-174
Publication statusPublished - 2005

Fingerprint Dive into the research topics of 'Lower bounds for kinetic sorting'. Together they form a unique fingerprint.

Cite this