TY - JOUR

T1 - Two Approaches to Building Time-Windowed Geometric Data Structures

AU - Chan, Timothy M.

AU - Hershberger, John

AU - Pratt, Simon

N1 - Funding Information:
We wish to thank Haim Kaplan and Micha Sharir for their suggestions, which led to an improvement of an earlier version of Lemma?3.1.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 et al. (in: Proceedings of the 31st International Symposium on Computational Geometry (SoCG), pp 240–254, 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 both the time-windowed 2D diameter decision problem and the time-windowed 2D convex hull area decision problem in O(nlog n) time, improving Bokal et al. ’s O(nlog 2n) and O(nlog nlog 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 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(npolylogn) algorithms for the time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems.

AB - 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 et al. (in: Proceedings of the 31st International Symposium on Computational Geometry (SoCG), pp 240–254, 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 both the time-windowed 2D diameter decision problem and the time-windowed 2D convex hull area decision problem in O(nlog n) time, improving Bokal et al. ’s O(nlog 2n) and O(nlog nlog 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 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(npolylogn) algorithms for the time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems.

KW - Dynamic convex hull

KW - Geometric data structures

KW - Range searching

KW - Time window

UR - http://www.scopus.com/inward/record.url?scp=85066801929&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85066801929&partnerID=8YFLogxK

U2 - 10.1007/s00453-019-00588-3

DO - 10.1007/s00453-019-00588-3

M3 - Article

AN - SCOPUS:85066801929

JO - Algorithmica (New York)

JF - Algorithmica (New York)

SN - 0178-4617

ER -