Back to search

University of British Columbia

Computational geometry on an integer grid

Abstract

dc:description

In this thesis we study a number of geometric problems in an integer grid domain. The worst case time complexity of many of the algorithms that solve geometric problems in the real plane is O(nlogn). This lower time bound is often proved by comparing the problems to Ω(nlogn) time comparison sorting. In the grid domain it is possible to sort coordinates, distances and angles in linear time. By taking advantage of linear integer grid sorting capabilities we are able to present linear time algorithms for the following geometric problems which have 0(nlogn) time algorithms when set in the real plane: finding the convex hull of n points, finding a simple closed polygonal path through n points, finding the diameter of a set of n points, deciding the separability question for two point sets, finding the smallest enclosing circle for a set of points, finding a triangulation of a set of n points and finding the Voronoi polygon of one of a set of n points. We extend van Emde Boas' O(nloglogn) integer set manipulation tree structure so it will work on the O(n[sup k]) size integer grid. Using this extended structure we are able to present O(loglogn) search time algorithms for the problems of searching for a test point in a set of rectangles, in a rectilinear planar subdivision and in a restricted angle subdivision. We are also able to use the extended van Emde Boas tree to present O(nloglogn) time algorithms for the following intersection problems on the grid: detecting whether any two of n rectangles intersect, detecting whether any two of n rectilinear polygons intersect and detecting whether any two of n restricted angle polygons intersect.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1980

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Keil, J. Mark

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/22142

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Keil, J. Mark. Computational geometry on an integer grid. master's thesis, University of British Columbia, 1980. http://hdl.handle.net/2429/22142