The field of computational geometry has been very successful in the development of efficient algorithms for computational problems in 2- and 3-dimensional space, but extensions to higher dimensions often suffer due to the rapid growth of combinatorial complexity. This has led to interest in approximation algorithms, where an approximation parameter is given, and the algorithm provides a solution that is accurate to within the desired degree of precision. In this series of lectures, I will introduce a number of computational methods and discrete geometric structures that have been shown to be successful in tackling multi-dimensional geometric problems. This will include a survey of established tools, such as well-separated pair decompositions, approximate Voronoi diagrams, convex approximations based on the Lowner-John ellipsoid, coresets, and Macbeath regions. It will also include recent developments, including the application of these techniques to approximate nearest-neighbor searching, approximate Euclidean minimum spanning trees, output-sensitive algorithms for coresets, and approximate polytope membership queries.

Brief 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 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, ACM Trans. on Mathematical Software, Computational Geometry: Theory and Applications, International Journal of Computational Geometry & Applications, and has served on the editorial board of Pattern Recognition. He was the conference chair for the 24th Annual Symposium on Computational Geometry in 2008. He is currently serving on the Computational Geometry Steering Committee.