Kinetic and dynamic data structures for convex hulls and upper envelopes

DOI10.1016/j.comgeo.2006.01.002zbMath1106.65014OpenAlexW1977401387MaRDI QIDQ857064

Haim Kaplan, Micha Sharir, Giora Alexandron

Publication date: 14 December 2006

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2006.01.002

zbMATH Keywords

Davenport-Schinzel sequences

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Data structures (68P05)

Related Items

Kinetic Euclidean minimum spanning tree in the plane, A kinetic triangulation scheme for moving points in the plane, Out-of-order event processing in kinetic data structures, Agglomerative clustering of growing squares, A simple, faster method for kinetic proximity problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kinetic collision detection with fast flight plan changes
• Maintenance of configurations in the plane
• Improved bounds for planar \(k\)-sets and related problems
• Discrete mobile centers
• Kinetic collision detection between two simple polygons.
• Cylindrical static and kinetic binary space partitions
• Lower bounds for kinetic planar subdivisions
• Randomized search trees
• Data Structures for Mobile Data
• KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS
• Algorithms - ESA 2003
• Kinetic connectivity for unit disks
• Point sets with many \(k\)-sets
• Maintaining the extent of a moving point set