We study geometric data structures for sets of point-based temporal events, such as geo-tagged scientific observations, sporting actions, or disaster responses, so as to answer real-time time-windowed queries, each of which is specified by a range of event times, [t1,t2], and a geometric question to be answered for the contiguous subsequence of point events with time stamps in this range. In particular, we consider time-windowed queries for skylines in ℝd and convex hulls in ℝ2. For skyline problems, we provide a data structure using near-linear space and preprocessing that can report the skyline in time proportional to its size. For convex hull problems, we provide a data structures using near-linear space and preprocessing that can in polylogarithmic time answer various convex hull queries, including gift wrapping, hull reporting, tangent finding, linear programming, line decision, line stabbing, membership, and containment.
(Joint work with Michael J. Bannister, William E. Devanny, Michael T. Goodrich, and Joseph A. Simons)