Kinetic sorting and kinetic convex hulls
type: Item
instance of: scholarly article
title: Kinetic sorting and kinetic convex hulls
zbMATH Open document ID: 1113.65017
author: Mohammad A. Abam
author: Mark de Berg
published in: Computational Geometry
publication date: 2007-03-15T00:00:00Z
review text: 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.
reviewed by: Ljubiša Kocić
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 5134246
zbMATH Keywords: Computational geometry
zbMATH Keywords: Kinetic data structures
zbMATH Keywords: Kinetic sorting
zbMATH Keywords: Lower bounds
zbMATH Keywords: Kinetic convex hulls
MaRDI profile type: Publication
full work available at URL: j.comgeo.2006.02.004
OpenAlex ID: W2205245699
cites work: Indexing moving points
cites work: Algorithms – ESA 2004
cites work: Q4778542
cites work: Lower bounds for kinetic planar subdivisions
cites work: Q4411341
cites work: Maintaining the extent of a moving point set
cites work: Maintaining approximate extent measures of moving points
cites work: Data Structures for Mobile Data
cites work: Algorithms - ESA 2003
cites work: Q4344150
cites work: Q4499944
cites work: Kinetic connectivity for unit disks
cites work: Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons
cites work: Reporting points in halfspaces
cites work: On ray shooting in convex polytopes
cites work: Q4226695
DOI: 10.1016/J.COMGEO.2006.02.004
description: scientific article; zbMATH DE number 5134246