Open Collections

Computational geometry on an integer grid

University of British Columbia

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.

Text

2010-03-19

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.

http://hdl.handle.net/2429/22142

Computer Science

University of British Columbia

Graduate