Two approaches to building time-windowed geometric data structures

DOI10.1007/s00453-019-00588-3zbMath1429.68048OpenAlexW2947017200WikidataQ127760969 ScholiaQ127760969MaRDI QIDQ2319633

Simon Pratt, Timothy M. Chan, J. E. Hershberger

Publication date: 20 August 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5920/

zbMATH Keywords

range searchingtime windowgeometric data structuresdynamic convex hull

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Dynamic convex hulls under window-sliding updates, Faster algorithms for largest empty rectangles and boxes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Two-dimensional range successor in optimal time and almost linear space
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• Maintenance of configurations in the plane
• Off-line dynamic maintenance of the width of a planar point set
• Applications of a semi-dynamic convex hull algorithm
• Applications of random sampling in computational geometry. II
• Dynamic half-space range reporting and its applications
• Persistent Predecessor Search and Orthogonal Point Location on the Word RAM
• Dynamic planar convex hull operations in near-logarithmic amortized time
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• On the convex layers of a planar set
• An optimal real-time algorithm for planar convex hulls
• Incremental and Decremental Maintenance of Planar Width
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• A fully dynamic algorithm for planar
• Finding All Maximal Subsequences with Hereditary Properties
• Orthogonal range searching on the RAM, revisited