Back to search

Carleton University

Partial Enclosure Range Searching

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Master of Computer Science (M.C.S.)
Level thesis:degree_level
Master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Carleton University
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bint, Gregory

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Carleton University
Base URL
carleton.scholaris.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bint, Gregory. Partial Enclosure Range Searching. Master's thesis, Carleton University, 2015. https://hdl.handle.net/20.500.14718/42101