Two approaches to building time-windowed geometric data structures
type: Item
instance of: scholarly article
title: Two approaches to building time-windowed geometric data structures
zbMATH Open document ID: 1429.68048
author: Timothy M. Chan
author: Simon Pratt
author: John Hershberger
published in: Algorithmica
publication date: 2019-08-20T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5920/
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 7096138
zbMATH Keywords: geometric data structures
zbMATH Keywords: time window
zbMATH Keywords: range searching
zbMATH Keywords: dynamic convex hull
MaRDI profile type: Publication
OpenAlex ID: W2947017200
cites work: Dynamic half-space range reporting and its applications
cites work: Off-line dynamic maintenance of the width of a planar point set
cites work: Finding All Maximal Subsequences with Hereditary Properties
cites work: Dynamic planar convex hull operations in near-logarithmic amortized time
cites work: A fully dynamic algorithm for planar
cites work: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
cites work: Persistent Predecessor Search and Orthogonal Point Location on the Word RAM
cites work: Q5088951
cites work: Orthogonal range searching on the RAM, revisited
cites work: Q3132862
cites work: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
cites work: On the convex layers of a planar set
cites work: Fractional cascading. I: A data structuring technique
cites work: Fractional cascading. II: Applications
cites work: Applications of random sampling in computational geometry. II
cites work: Incremental and Decremental Maintenance of Planar Width
cites work: Q3138936
cites work: Applications of a semi-dynamic convex hull algorithm
cites work: Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
cites work: Maintenance of configurations in the plane
cites work: An optimal real-time algorithm for planar convex hulls
cites work: Q3992847
cites work: Two-dimensional range successor in optimal time and almost linear space
Wikidata QID: Q127760969
DOI: 10.1007/S00453-019-00588-3
Recommended article: Q3132862
Recommended article: Time Windowed Data Structures for Graphs
Recommended article: Q4945511
Recommended article: Efficient structures for geometric data management
Recommended article: Dynamic geometric data structures via shallow cuttings
Recommended article: Q5088951
Recommended article: Temporal matching on geometric graph data
Recommended article: Succinct and Implicit Data Structures for Computational Geometry
Recommended article: Towards in-place geometric algorithms and data structures
description: scientific article