David Mount

David Mount is a professor at University of Maryland Department of Computer Science (College Park Campus) whose research is in Computational Geometry.

Biography

Mount received a B.S. in Computer Science at Purdue University in 1977 and received his Ph.D. in Computer Science at Purdue University in 1983 under the advisement of Christoph Hoffmann.

He began teaching at the University of Maryland in 1984 and is Professor in the department of Computer Science there.^[1]

As a teacher, he has won the University of Maryland, College of Computer Mathematical and Physical Sciences Dean's Award for Excellence in Teaching in 2005 and 1997 as well as other teaching awards including the Hong Kong Science and Technology, School of Engineering Award for Teaching Excellence Appreciation in 2001.

Research

Mounts's main area of research is Computational Geometry, which is the branch of algorithms devoted to solving problems of a geometric nature. This field includes problems from classic geometry, like the closest pair of points problem, as well as more recent applied problems, such as computer representation and modeling of curves and surfaces. In particular, Mount has worked on the k-means clustering problem, nearest neighbor search, and point location.

Mount has worked on developing practical algorithms for k-means clustering, a problem known to be NP-hard. The most common algorithm used is Lloyd's algorithm, which is heuristic in nature but performs well in practice. He and others later showed ^[2] how kd-trees could be used to speed up Lloyd's algorithm. They have implemented this algorithm, along with some additional improvements, in the software library Kmeans.

Mount has worked on the nearest neighbor and approximate nearest neighbor search problems. By allowing the algorithm to return an approximate solution to the nearest neighbor query, a significant speedup in space and time complexity can be obtained. One class of approximate algorithms takes as input the error distance, $\epsilon$, and forms a data structure that can be stored efficiently (low space complexity) and that returns the $(1+\epsilon)$-approximate nearest neighbor quickly (low time complexity). In co-authored work with Arya, Netanyahu, Silverman, and Wu,^[3] Mount showed that the approximate nearest neighbor problem could be solved efficiently in spaces of low dimension. The data structure described in that paper formed the basis of the ANN library, which is a popular open-source library for approximate nearest neighbor searching.^[4] In subsequent work, he investigated the computational complexity of approximate nearest neighbor searching. Together with co-authors Arya and Malamatos, he provided efficient space-time tradeoffs for approximate nearest neighbor searching,^[5] based on a data structure called the AVD (or approximate Voronoi diagram).

Mount has also worked on point location, which involves preprocessing a planar polygonal subdivision S of size $n$ to determine the cell of a subdivision that a query point is in. In,^[6] the paper gives an $O(n log n)$ time to construct a data structure of $O(n)$ space that when asked what cell a query point lies in, takes expected time $H + O(\sqrt{H} + 1)$ where $H$ is the entropy of the probability distribution of which cells the query points lie in.

In addition to the design and analysis of algorithms in computational geometry, Mount has worked on the implementation of efficient algorithms in software libraries such as:

• ANN - approximate nearest neighbor searching
• ISODATA - efficient implementation of a popular clustering algorithm
• KMeans - k-means clustering

Most cited works

As of December 8, 2009, here is a list of his most cited works (according to Google Scholar) and their main contributions, listed in decreasing order of citations:

1. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions^[3] - In this paper they give a n $O(c_{d,\epsilon}\log(n))$ algorithm (where $c_{d,\epsilon}$ depends on both the number of dimensions $d$ and the approximate error $\epsilon$) to find a neighbor that is at most a factor $(1 + \epsilon)$ distance from the nearest neighbor.
2. An Efficient k-Means Clustering Algorithm: Analysis and Implementation^[2] - In this paper they provide a simpler and more efficient implementation of Lloyd's Algorithm, which is used in k-means clustering, The algorithm is called the filtering algorithm.
3. The Discrete Geodesic Problem^[7] - In this paper they compute the shortest path from a source to a destination constrained to having to travel on the surface of a given (possibly nonconvex) polyhedron. Their algorithm takes $O(n^2 \log(n))$ time to find the first shortest path to the first destination and the shortest path to any additional destination (from the same source) can be computed in $O(\log n)$ time. Here, $n$ is the number of vertices.

References

1. D. Mount. Curriculum Vitae
2. T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman and A. Y. Wu. An Efficient k-Means Clustering Algorithm: Analysis and Implementation. IEEE Trans. Pattern Analysis and Machine Intelligence 24(7):881-–892, 2002.
3. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Wu, '"n Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions", Journal of the ACM, 45(6):891-923, 1998.
4. D. M. Mount and S. Arya, ANN: A Library for Approximate Nearest Neighbor Searching
5. S. Arya, S., T. Malamatos, and D. M. Mount. Space-time Tradeoffs for Approximate Nearest Neighbor Searching. Journal of the ACM, 57(1): 1-54, 2009
6. S. Arya, T. Malamatos, D. M. Mount and K. C. Wong. Optimal Expected-Case Planar Point Location. Siam Journal on Computing, 37(2):584-610, 2007.
7. J. S. B. Mitchell, D. M. Mount and C. H. Papadimitriou. The Discrete Geodesic Problem. Siam Journal of Computing, 16(4):647-668, 1987

External links

• Official website
• Data Structures and Algorithms in C++