Recently, a series of seminal results has established the central role that convex approximation plays in solving a number of computational problems in Euclidean spaces of constant dimension. These include fundamental applications such as computing the diameter of a point set, Euclidean minimum spanning trees, bichromatic closest pairs, width kernels, and nearest neighbor searching. In each case, an approximation parameter eps is given, and the problem is to compute a solution that is within a factor of 1+ eps of the exact solution. In this talk, I will present recent approaches to convex approximation. These approaches achieve efficiency by being locally sensitive to the shape and curvature of the body. This is achieved through a combination of methods, both new and classical, including Delone sets in the Hilbert metric, Macbeath regions, and John ellipsoids. We will explore the development of these methods and discuss how they can be applied to the above problems.
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 150 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 a number of journals, including ACM Transactions on Spatial Algorithms and Systems, Computational Geometry: Theory and Applications, International Journal of Computational Geometry & Applications, and he has served on the editorial boards of ACM Trans. on Mathematical Software and Pattern Recognition. He was the conference chair for the 24th Annual Symposium on Computational Geometry in 2008. 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 and SPIE's Conferences on Vision Geometry from 2001 through 2006. He is currently serving on the Computational Geometry Steering Committee.
He has won a number of awards for excellence in teaching, including twice winning the University of Maryland's College of Computer, Mathematical and Natural 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.