Return to search

Application of computational geometry to pattern recognition problems

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.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.28373
Date January 1981
CreatorsBhattacharya, Binay K.
ContributorsGodfried T. Toussaint (advisor)
PublisherMcGill University
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
Formatapplication/pdf
CoverageDoctor of Philosophy (School of Computer Science)
RightsAll items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated.
Relationalephsysno: 000139880, proquestno: NK58111, Theses scanned by UMI/ProQuest.

Page generated in 0.0022 seconds