Windowing queries using Minkowski sum and their extension to MapReduce

Given a set of n segments and a query shape Q, the windowing length query asks for finding the sum of the lengths of the parts of the segments that lie inside Q. The popular places problem of a set of curves asks for the subset of the plane where each query shape centered at a point of that region intersects with at least f distinct curves. For square queries, an optimal \(O(n^2)\) time algorithm and a matching lower bound exist. We solve the length query problem for convex polygons and disks as query shapes, with \(O(\log n+k)\) query time and polynomial preprocessing time that depends on the complexity of the query shape. We define a new version of the problem of finding popular places in a set of trajectories where the center of a query is a popular place if the length of the curves inside that query is at least f and use our data structure to solve the original problem as well as this new version. Other than length queries, we solve reporting queries that return the set of intersected segments. For disk queries, we design a point-location data structure for congruent disks with \(O(\log n)\) query time and \(O(n^3\log n)\) preprocessing. We also give algorithms for computing the length query for c-packed curves, which are a class of curves for which the length of the curve inside a disk of radius r is upper-bounded by cr, where c is a constant. Also, we use length queries for polygons to approximate the minimum value c for which a curve is c-packed, if such a c exists. Our results extend to MRC and MPC models for MapReduce, where we address these problems on a set of x-monotone curves. The round complexities of our MapReduce algorithms are constant. In addition, we also implemented our popular places algorithms on trajectories on inputs as big as 15K points to evaluate the efficiency of our algorithms in practice.