In this paper, we examine the problem of efficiently computing a class of aggregate functions on regions of space. We first formalize region-based aggregations for a large class of efficient geometric aggregations. The idea is to represent the query object with pre-defined objects with set operations, and compute the aggregation using the pre-computed aggregation values. We first show that it applies to existing results about points and rectangular objects. Since it is defined using set theory instead of object shapes, it can be applied to polygons. Given a database D of polygonal regions, a tessellation T of the plane, and a query polygon q constructed from T, we prove that the aggregation of q can be calculated by the aggregation over triangles and lines constructed from segments and vertices in q, which can be pre-computed. The query time complexity is O(klogn), where k is the size of query polygon and n is the size of T.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.