| In this thesis it is shown that several pattern recognition problems can be solved efficiently by exploiting the geometrical structure of the problems. The problems considered are in the area of clustering and classification. These problems are: (i) computing the diameter of a finite planar set, (ii) computing the maximum and minimum distance between two finite planar sets of points, (iii) testing for point inclusion in a convex polyhedron in d-dimensional space, and (iv) exact and inexact reference set thinning for the nearest neighbor decision rule.; Algorithms to solve the above problems are presented and analyzed for worst-case and average-case situations. These algorithms are implemented and experimentally compared with the existing algorithms.; In solving the above problems, a geometrical construct, known as the Voronoi diagram is used extensively. However, there exists no practical algorithm to construct the Voronoi diagram in d dimensional spaces when d > 2. In this thesis an efficient algorithm to construct the Voronoi diagram in d-space is presented. |
