Dynamic data structures for fat objects and their applications

We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in or. Our planar structures are actually fitted for a more general class of objects – (β,δ)-covered objects – which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.