Range-Aggregate Queries for Geometric Extent Problems

Brass, P., Knauer, C., Shin, C. and Smid, M.

    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.
Cite as: Brass, P., Knauer, C., Shin, C. and Smid, M. (2013). Range-Aggregate Queries for Geometric Extent Problems. In Proc. Theory of Computing 2013 (CATS 2013) Adelaide, Australia. CRPIT, 141. Wirth, A. Eds., ACS. 3-10
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS