Kinetic sorting and kinetic convex hulls

M.A. Abam, M. Berg, de

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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(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?).
Original languageEnglish
Pages (from-to)16-26
JournalComputational Geometry
Volume37
Issue number1
DOIs
Publication statusPublished - 2007

Fingerprint Dive into the research topics of 'Kinetic sorting and kinetic convex hulls'. Together they form a unique fingerprint.

  • Cite this