You are here

Algorithms for Solving Near Point Problems

Title: Algorithms for Solving Near Point Problems.
67 views
20 downloads
Name(s): Connor, Michael, author
Kumar, Piyush, professor directing thesis
Mio, Washington, university representative
Li, Feifei, committee member
Liu, Xiuwen, committee member
Department of Computer Science, degree granting department
Florida State University, degree granting institution
Type of Resource: text
Genre: Text
Issuance: monographic
Date Issued: 2011
Publisher: Florida State University
Place of Publication: Tallahassee, Florida
Physical Form: computer
online resource
Extent: 1 online resource
Language(s): English
Abstract/Description: Near point problems are widely used in computational geometry as well as a variety of other scientific fields. This work examines four common near point problems and presents original algorithms that solve them. Planar nearest neighbor searching is highly motivated by geographic information system and sensor network problems. Efficient data structures to solve near neighbor queries in the plane can exploit the extreme low dimension for fast results. To this end, DealaunayNN is an algorithm using Delaunay graphs and Voronoi cells to answer queries in O(log n) time, faster in practice than other common state-of-the art algorithms. k-Nearest neighbor graph construction arises in computer graphics in areas of normal estimation and surface simplification. This work presents knng, an efficient algorithm using Morton ordering to solve the problem. The knng algorithm exploits cache coherence and low storage space, as well as being extremely optimize-able for parallel processors. The GeoFilterKruskal algorithm solves the problem of computing geometric minimum spanning trees. A common tool in tackling clustering problems, GMSTs are an extension of the minimum spanning tree graph problem, applied to the complete graph of a point set. By using well separated pair decomposition, bi-chromatic closest pair computation, and partitioning and filtering techniques, GeoFilterKruskal greatly reduces the total computation required. It is also one of the only algorithms to compute GMSTs in a manner that lends itself to parallel computation; a major advantage over its competitors. High dimensional nearest neighbor searching is an expensive operation, due to an exponential dependence on dimension from many lower dimensional solutions. Modern techniques to solve this problem often revolve around projecting data points into a large number of lower dimensional subspaces. PCANN explores the idea of picking one particularly relevant subspace for projection. When used on SIFT data, principal component analysis allows for greatly reduced dimension with no need for multiple projection. Additionally, this algorithm is also highly motivated to make use of parallel computing power.
Identifier: FSU_migr_etd-3440 (IID)
Submitted Note: A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
Degree Awarded: Spring Semester, 2011.
Date of Defense: April 4, 2011.
Keywords: Near neighbor, Computational geometry, Algorithms
Bibliography Note: Includes bibliographical references.
Advisory Committee: Piyush Kumar, Professor Directing Thesis; Washington Mio, University Representative; Feifei Li, Committee Member; Xiuwen Liu, Committee Member.
Subject(s): Computer science
Persistent Link to This Record: http://purl.flvc.org/fsu/fd/FSU_migr_etd-3440
Owner Institution: FSU

Choose the citation style.
Connor, M. (2011). Algorithms for Solving Near Point Problems. Retrieved from http://purl.flvc.org/fsu/fd/FSU_migr_etd-3440