Chan, Timothy M. ;
Pratt, Simon
Two Approaches to Building TimeWindowed Geometric Data Structures
Abstract
Given a set of geometric objects each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems timewindowed decision problems, and they have been the subject of much recent attention, for instance studied by Bokal, Cabello, and Eppstein [SoCG 2015]. In this paper, we present new approaches to this class of problems that are conceptually simpler than Bokal et al.'s, and also lead to faster algorithms. For instance, we present algorithms for preprocessing for the timewindowed 2D diameter decision problem in O(n log n) time and the timewindowed 2D convex hull area decision problem in O(n alpha(n) log n) time (where alpha is the inverse Ackermann function), improving Bokal et al.'s O(n log^2 n) and O(n log n loglog n) solutions respectively.
Our first approach is to reduce timewindowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our other approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is near linear for any FIFO update sequence, in which deletions occur in the same order as insertions. We also apply these approaches to obtain the first O(n polylog n) algorithms for the timewindowed 3D diameter decision and 2D orthogonal segment intersection detection problems.
BibTeX  Entry
@InProceedings{chan_et_al:LIPIcs:2016:5920,
author = {Timothy M. Chan and Simon Pratt},
title = {{Two Approaches to Building TimeWindowed Geometric Data Structures}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {28:128:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5920},
URN = {urn:nbn:de:0030drops59201},
doi = {10.4230/LIPIcs.SoCG.2016.28},
annote = {Keywords: time window, geometric data structures, range searching, dynamic convex hull}
}
2016
Keywords: 

time window, geometric data structures, range searching, dynamic convex hull 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 