dc.contributor.advisor Fussell, Donald S., 1951- en dc.contributor.advisor Amenta, Annamaria B. en dc.creator Choi, Sunghee en dc.date.accessioned 2008-08-28T21:24:30Z en dc.date.available 2008-08-28T21:24:30Z en dc.date.issued 2003 en dc.identifier b56732107 en dc.identifier.uri http://hdl.handle.net/2152/505 en dc.description text en dc.description.abstract The Delaunay triangulation is one of the fundamental problems in computational geometry, dual to the well-known Voronoi diagram. It has numerous applications in various disciplines such as computer graphics, computer vision, and robotics. This thesis deals with a number of interrelated questions arising in modeling shapes by computing Delaunay triangulations. We give algorithms for surface reconstruction, computing Delaunay triangulations given surfaces, and computing Delaunay triangulations in general. Given a set of samples from a surface, the surface reconstruction problem is to construct a piecewise linear approximation of the original surface. We give two surface reconstruction algorithms with guarantees of both geometric and topological correctness using the 3D Delaunay triangulation of the input samples. The first algorithm selects a set of Delaunay triangles using a simple geometric test and extracts a manifold from it. It is the first surface reconstruction algorithm with topological guarantee of correctness. The second algorithm improves the robustness using the weighted Voronoi diagrams called power diagram. When the surface on which the samples lie are known, we can use the connectivity of the surface to speed up the Delaunay triangulation. We give an O(n log∗ n) expected time algorithm to compute the 3D Delaunay triangulation given the surface on which the samples lie, under some realistic assumptions. It improves upon O(n log n) expected time usual randomized incremental algorithm in this case. The algorithm can be useful for mesh generation and medial axis construction. The randomized incremental algorithm for Delaunay triangulation is theoretically optimal in expected time but suffers from serious thrashing because of its random memory access pattern when the data structure gets too large to fit in memory. We propose a new insertion order called biased randomized insertion order (BRIO) which removes enough randomness to significantly improve performance, but leaves enough randomness so that the algorithm remains theoretically optimal. We show by experiments that the size of input data we can compute in a given machine increases dramatically using BRIO instead of the total random order. dc.format.medium electronic en dc.language.iso eng en dc.rights Copyright is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works. en dc.subject.lcsh Triangulation en dc.subject.lcsh Geometry--Data processing en dc.title Practical Delaunay triangulation algorithms for surface reconstruction and related problems en dc.description.department Computer Sciences en dc.identifier.oclc 55991131 en dc.identifier.proqst 3110760 en dc.type.genre Thesis en thesis.degree.department Computer Sciences en thesis.degree.discipline Computer Sciences en thesis.degree.grantor The University of Texas at Austin en thesis.degree.level Doctoral en thesis.degree.name Doctor of Philosophy en
﻿