Award Date

8-1-2012

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Laxmi P. Gewali

Second Committee Member

Ajoy K. Datta

Third Committee Member

John T. Minor

Fourth Committee Member

Rama Venkat

Number of Pages

57

Abstract

Triangulation of simple polygons or sets of points in two dimensions is a widely investigated problem in computational geometry. Some researchers have considered variations of triangulation problems that include minimum weight triangulation, de-launay triangulation and triangulation refinement. In this thesis we consider a constrained version of the triangulation problem that asks for triangulating a given domain (polygon or point sites) so that the resulting triangulation has an increased number of even degree vertices. This problem is called Degree Constrained Triangulation (DCT). We propose four algorithms to solve DCT problems. We also present experimental results based on the implementation of the proposed algorithms. The implementation is done in Java programming language with user friendly graphical interface.

Keywords

Degree constrained; Delaunay-Flip; Even degree; Flipping; Geometry; Scan-Flip; Triangulation

Disciplines

Computer Sciences | Geometry and Topology | Numerical Analysis and Computation | Theory and Algorithms

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS