Theory and Algorithms Commons^™

Efficient Estimation Of Cluster Population, Sanjeev K C

UNLV Theses, Dissertations, Professional Papers, and Capstones

Partitioning a given set of points into clusters is a well known problem in pattern recognition, data mining, and knowledge discovery. One of the well known methods for identifying clusters in Euclidean space is the K-mean algorithm. In using the K-mean clustering algorithm it is necessary to know the value of k (the number of clusters) in advance. We propose to develop algorithms for good estimation of k for points distributed in two dimensions. The techniques we pursue include a bucketing method, g-hop neighbors, and Voronoi diagrams. We also present experimental results for examining the performances of the bucketing method …

Approaches For Generating 2d Shapes, Pratik Shankar Hada

UNLV Theses, Dissertations, Professional Papers, and Capstones

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 …

Degree Constrained Triangulation, Roshan Gyawali

UNLV Theses, Dissertations, Professional Papers, and Capstones

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 …

Sharp Feature Identification In A Polygon, Joseph P. Scanlan

UNLV Theses, Dissertations, Professional Papers, and Capstones

This thesis presents an efficient algorithm for recognizing and extracting sharp-features from polygonal shapes. As used here, a sharp-feature is a distinct portion of a polygon that is long and skinny. The algorithm executes in O(n^2) time, where n is the number of vertices in the polygon. Experimental results from a Java implementation of the algorithm are also presented.