Let S be a set of n points in the plane. We present data structures that solve range-aggregate query problems on three geometric extent measure problems. Using these data structures, we can report, for any axis-parallel query rectangle Q, the area/perimeter of the convex hull, the width, and the radius of the smallest enclosing disk of the points in S ∩ Q.

Additional Metadata
Keywords Computational geometry, Convex hull, Orthogonal range query, Range-aggregate query, Smallest enclosing disk, Width
Conference Computing: The Australasian Theory Symposium, CATS 2013
Citation
Brass, P. (Peter), Knauer, C. (Christian), Shin, C.-S. (Chan-Su), Smid, M, & Vigan, I. (Ivo). (2013). Range-aggregate queries for geometric extent problems. Presented at the Computing: The Australasian Theory Symposium, CATS 2013.