Partial Enclosure Range Searching

Public Deposited
Resource Type
  • 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.

Thesis Degree Level
Thesis Degree Name
Thesis Degree Discipline
Rights Notes
  • Copyright © 2015 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
Date Created
  • 2015


In Collection: