Award Date

8-1-2014

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Laxmi P. Gewali

Second Committee Member

John Minor

Third Committee Member

Ajoy Datta

Fourth Committee Member

Rama Venkat

Number of Pages

50

Abstract

Constructing a two dimensional shape from given a set of point sites is a well known problem in computation geometry. We present a critical review of the existing algorithms for constructing polygonal shapes. We present a new approach calledinward dentingfor constructing simple polygons. We then extend the proposed approach for modeling polygons with holes. This is the

first known algorithm for modeling holes in the interior of 2d shapes. We also present experimental investigations of the quality of the solutions generated by the proposed algorithms.

For this we implemented the proposed algorithms in Java programming language. The prototype program can be executed by users to enter point sites interactively. The experimental results show that the perimeter of the generated shape is at most 33% more than the length of the minimum spanning tree.

Keywords

Computational Geometry; Convex Hull; Generation of geometric forms; Holes; Inward Denting; Polygons – Computer simulation; Random Generation Polygon

Disciplines

Computer Sciences | Geometry and Topology | 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