We present data structures that can answer window queries for a sequence of geometric objects, such as points, line segments, triangles and convex c-gons. We first present data structures to solve windowed intersection decision problems using line segments, triangles and convex c-gons. We also present data structures to count points on maximal layer, to decide whether a given point belongs to a maximal layer, and to count k-dominant points for a fixed integer k for a sequence of points in Rd, d≥2. All data structures presented in this paper answer queries in polylogarithmic time and use subquadratic space.

Additional Metadata
Keywords Intersection decision problem, Maximal layer, Maximal point, Window query
Persistent URL dx.doi.org/10.1007/978-3-319-74180-2_17
Series Communications in Computer and Information Science
Citation
Chanchary, F. (Farah), Maheshwari, A, & Smid, M. (2018). Window queries for problems on intersecting objects and maximal points. In Communications in Computer and Information Science. doi:10.1007/978-3-319-74180-2_17