Approximate Nearest Neighbor Searching and Polytope Approximation

GRAND Seminar September 26, 1 PM, Wed., 2012, ENGR 4201

David M. Mount
Professor
Department of Computer Science
University of Maryland

Abstract:

Nearest neighbor searching is among the most fundamental retrieval problems in geometry. Given a large set of points in d-dimensional space and a query point q, find the closest point of the set to q. Nearest neighbor queries arise in numerous applications of science and engineering, including pattern recognition, machine learning, computer graphics, and geographic information systems. Provably efficient solutions are known in only one- and two-dimensional space, and research over two decades has focused on solving the problem approximately.

In this talk I will survey developments in approximate nearest neighbor searching in Euclidean space of constant dimension. Recent work on establishing the best computational bounds has been based on the solution to a completely different problem, namely approximating a convex polytope with a minimum number of facets. We will see how a number of classical concepts from convex geometry can be applied to obtain the best known bounds for approximate nearest neighbor searching.

Short Bio:

David Mount is a professor in the Department of Computer Science at the University of Maryland with a joint appointment in the University's Institute for Advanced Computer Studies (UMIACS). He received his Ph.D. from Purdue University in Computer Science in 1983, and started at the University of Maryland in 1984. In 2001 he was a visiting professor at the Hong Kong University of Science and Technology.

He has written over 140 research publications on algorithms for geometric problems, particularly problems with applications in image processing, pattern recognition, information retrieval, and computer graphics. He currently serves on the editorial boards of ACM Transactions on Mathematical Software, Computational Geometry: Theory and Applications, and the International Journal on Computational Geometry and Applications. He served on the editorial board of Pattern Recognition from 1999 to 2006. He has served on the program committees of many of the major conferences in his area, and he served as the program committee co-chair for the 19th ACM Symposium on Computational Geometry in 2003 and the Fourth Workshop on Algorithm Engineering and Experiments in 2002.

He has won a number of awards for excellence in teaching, including twice winning the University of Maryland's College of Computer, Mathematical and Physical Sciences, Dean's Award for Excellence in Teaching, and the Award for Teaching Excellence Appreciation in 2001 at the Hong Kong University of Science and Technology. He has co-authored the textbook Data Structures and Algorithms in C++ with Mike Goodrich and Roberto Tamassia.