Open Collections

Dynamic problems in computational geometry

University of British Columbia

Computational geometry is the study of algorithms for manipulating sets of points, lines, polygons, planes and other geometric objects. For many problems in this realm, the sets considered are static and the data structures representing them do not permit efficient insertion and deletion of objects (e.g. points). Dynamic problems, in which the set and the geometric data structure change over time, are also of interest. The topic of this thesis is the presentation of fast algorithms for fully dynamic maintenance of some common geometric structures. The following configurations are examined: planar nearest-point and farthest-point Voronoi diagrams, convex hulls (in two and three dimensions), common intersection of halfspaces (2-D and 3-D), and contour of maximal vectors (2-D and 3-D). The principal techniques exploited are fast merging of substructures, and the use of extra storage. Dynamic geometric search structures based upon the configurations are also presented.

Text

2010-03-24

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/22442

Computer Science

University of British Columbia

Graduate