Partial Enclosure Range Searching

This thesis examines a new type of range searching problem which we have called Partial Enclosure Range Searching. In this problem, given a set of geometric objects and a query region, our goal is to identify those objects where the size of their intersection with a query region is at least a fixed proportion of their original size. We consider several variations of this problem with different types of geometric objects and query regions. When querying line segments, this thesis presents methods for transforming the problem into one which can be solved using standard range searching techniques. When querying convex or monotone polygons, this thesis presents methods for calculating the area of the intersection between the polygon and a query rectangle, which can have uses outside of determining the partial enclosure property.