Two approaches to building time-windowed geometric data structures

Timothy M. Chan, Simon Pratt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 time-windowed 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 time-windowed 2D diameter decision problem in O(n log n) time and the time-windowed 2D convex hull area decision problem in O(nα(n) log n) time (where α is the inverse Ackermann function), improving Bokal et al.'s O(n log2 n) and O(n log n log log n) solutions respectively. Our first approach is to reduce time-windowed 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 time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems.

Original languageEnglish (US)
Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
EditorsSandor Fekete, Anna Lubiw
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages28.1-28.15
ISBN (Electronic)9783959770095
DOIs
StatePublished - Jun 1 2016
Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
Duration: Jun 14 2016Jun 17 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume51
ISSN (Print)1868-8969

Other

Other32nd International Symposium on Computational Geometry, SoCG 2016
CountryUnited States
CityBoston
Period6/14/166/17/16

Keywords

  • Dynamic convex hull
  • Geometric data structures
  • Range searching
  • Time window

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Two approaches to building time-windowed geometric data structures'. Together they form a unique fingerprint.

Cite this