Range-Aggregate Queries Involving Geometric Aggregation Operations

摘要

In this paper we consider range-aggregate query problems wherein we wish to preprocess a set S of geometric objects such that given a query orthogonal range q, a certain aggregation function on the objects S' = S ∩ q can be answered efficiently. Range-aggregate version of point enclosure queries, 1-d segment intersection, 2-d orthogonal segment intersection (with/without distancexonstraint) are revisited and we improve the existing results for these problems. We also provide semi-dynamic (insertions) solutions to some of these problems. This paper is the first attempt to provide dynamic solutions to problems involving geometric aggregation operations.