Show simple item record

dc.contributor.advisorFussell, Donald S., 1951-en
dc.contributor.advisorAmenta, Annamaria B.en
dc.creatorChoi, Sungheeen
dc.date.accessioned2008-08-28T21:24:30Zen
dc.date.available2008-08-28T21:24:30Zen
dc.date.issued2003en
dc.identifierb56732107en
dc.identifier.urihttp://hdl.handle.net/2152/505en
dc.descriptiontexten
dc.description.abstractThe 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.mediumelectronicen
dc.language.isoengen
dc.rightsCopyright 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.lcshTriangulationen
dc.subject.lcshGeometry--Data processingen
dc.titlePractical Delaunay triangulation algorithms for surface reconstruction and related problemsen
dc.description.departmentComputer Sciencesen
dc.identifier.oclc55991131en
dc.identifier.proqst3110760en
dc.type.genreThesisen
thesis.degree.departmentComputer Sciencesen
thesis.degree.disciplineComputer Sciencesen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophyen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record