Window queries for problems on intersecting objects and maximal points
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.
|Keywords||Intersection decision problem, Maximal layer, Maximal point, Window query|
|Series||Communications in Computer and Information Science|
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