A new approach to the dynamic maintenance of maximal points in a plane

DOI10.1007/BF02187797zbMath0714.68013MaRDI QIDQ751238

Susan Rodger, Greg N. Frederickson

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131124

zbMATH Keywords

dynamic contour search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Searching and sorting (68P10) Data structures (68P05)

Related Items (8)

I/O-efficient 2-d orthogonal range skyline and attrition priority queues ⋮ Dynamic layers of maxima with applications to dominating queries ⋮ Records, the maximal layer, and uniform distributions in monotone sets ⋮ On the dynamic maintenance of maximal points in the plane ⋮ Output-sensitive peeling of convex and maximal layers ⋮ Off-line dynamic maintenance of the width of a planar point set ⋮ Dynamic Planar Range Maxima Queries ⋮ An optimal online algorithm for halfplane intersection

Cites Work

• Maintenance of configurations in the plane
• Updating a balanced search tree in 0(1) rotations
• Adding range restriction capability to dynamic data structures
• On Finding the Maxima of a Set of Vectors

This page was built for publication: A new approach to the dynamic maintenance of maximal points in a plane