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. / Science, Faculty of / Computer Science, Department of / Graduate
| Identifer | oai:union.ndltd.org:UBC/oai:circle.library.ubc.ca:2429/22442 |
| Date | January 1981 |
| Creators | Gowda, Ihor George |
| Source Sets | University of British Columbia |
| Language | English |
| Detected Language | English |
| Type | Text, Thesis/Dissertation |
| 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. |
Page generated in 0.0018 seconds