Partial Enclosure Range Searching

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Bint, Gregory




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.


Computer Science




Carleton University

Thesis Degree Name: 

Master of Computer Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).