Kinetic and dynamic data structures for convex hulls and upper envelopes

DOI10.1016/J.COMGEO.2006.01.002MaRDI QIDQ857064zbMATH OpenOpenAlexFDO

Authors Giora Alexandron, Haim Kaplan, Micha Sharir

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

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

Recommendations

• Algorithms and Data Structures
• Kinetic sorting and kinetic convex hulls
• scientific article; zbMATH DE number 1617248
• Maintaining the extent of a moving point set
• Maintaining the extent of a moving point set

Cites work

• scientific article; zbMATH DE number 1303547 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1947377 (Why is no real title available?)
• scientific article; zbMATH DE number 1501063 (Why is no real title available?)
• scientific article; zbMATH DE number 1786516 (Why is no real title available?)
• Cylindrical static and kinetic binary space partitions
• Data Structures for Mobile Data
• Discrete mobile centers
• Improved bounds for planar k-sets and related problems
• KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS
• Kinetic collision detection between two simple polygons.
• Kinetic collision detection with fast flight plan changes
• Kinetic connectivity for unit disks
• Kinetic dictionaries: how to shoot a moving target
• Lower bounds for kinetic planar subdivisions
• Maintaining the extent of a moving point set
• Maintenance of configurations in the plane
• Point sets with many \(k\)-sets
• Randomized search trees
• Simplified kinetic connectivity for rectangles and hypercubes
• Soft kinetic data structures
• Static and kinetic geometric spanners with applications

Cited in

(20)

• Maintaining the extent of a moving point set
• Kinetic sorting and kinetic convex hulls
• Out-of-order event processing in kinetic data structures
• Kinetic collision detection with fast flight plan changes
• Algorithms and Data Structures
• Dynamic geometric data structures via shallow cuttings
• Kinetic convex hulls, Delaunay triangulations and connectivity structures in the black-box model
• A simple, faster method for kinetic proximity problems
• Kinetic sorting and kinetic convex hulls
• Kinetic Euclidean minimum spanning tree in the plane
• Kinetic convex hulls and Delaunay triangulations in the black-box model
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• scientific article; zbMATH DE number 7559224 (Why is no real title available?)
• Agglomerative clustering of growing squares
• A kinetic triangulation scheme for moving points in the plane
• Lower envelopes of surface patches in 3-space
• Maintaining the extent of a moving point set
• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Kinetic heap-ordered trees: Tight analysis and improved algorithms
• Robust Kinetic Convex Hulls in 3D

This page was built for publication: Kinetic and dynamic data structures for convex hulls and upper envelopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q857064)