Two approaches to building time-windowed geometric data structures

DOI10.1007/S00453-019-00588-3MaRDI QIDQ2319633zbMATH OpenOpenAlexWikidataFDO

Authors Timothy M. Chan, Simon Pratt, John 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

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

Recommendations

• Two approaches to building time-windowed geometric data structures
• Time windowed data structures for graphs
• scientific article; zbMATH DE number 1424298
• Efficient structures for geometric data management
• Dynamic geometric data structures via shallow cuttings
• scientific article; zbMATH DE number 7559224
• Temporal matching on geometric graph data
• Succinct and Implicit Data Structures for Computational Geometry
• Towards in-place geometric algorithms and data structures

Cites work

• scientific article; zbMATH DE number 432803 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 7559224 (Why is no real title available?)
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• A fully dynamic algorithm for planar
• An optimal real-time algorithm for planar convex hulls
• Applications of a semi-dynamic convex hull algorithm
• Applications of random sampling in computational geometry. II
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Dynamic half-space range reporting and its applications
• Dynamic planar convex hull operations in near-logarithmic amortized time
• Finding all maximal subsequences with hereditary properties
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• Incremental and Decremental Maintenance of Planar Width
• Maintenance of configurations in the plane
• Off-line dynamic maintenance of the width of a planar point set
• On the convex layers of a planar set
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Orthogonal range searching on the RAM, revisited
• Persistent predecessor search and orthogonal point location on the word RAM
• Two approaches to building time-windowed geometric data structures
• Two-dimensional range successor in optimal time and almost linear space

Cited in

(4)

• Dynamic convex hulls under window-sliding updates
• Two approaches to building time-windowed geometric data structures
• Window queries for problems on intersecting objects and maximal points
• Faster algorithms for largest empty rectangles and boxes

This page was built for publication: Two approaches to building time-windowed geometric data structures

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