MS-CS-L Archives

September 2012


Options: Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Jyh-Ming Lien <[log in to unmask]>
Reply To:
Thu, 20 Sep 2012 11:22:27 -0400
text/plain (94 lines)
[Apologies for multiple postings]

*    GRAND Seminar


Approximate Nearest Neighbor Searching and Polytope Approximation


September 26, 1 PM, Wednesday
ENGR 4201


David M. Mount
Department of Computer Science
University of Maryland


Jyh-Ming Lien


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

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

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

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.

Jyh-Ming Lien
Assistant Professor, George Mason University

MASC Group: