David Mount
Encyclopedia
David Mount is currently a Professor
at The University of Maryland (College Park Campus) whose research is in Computational Geometry
.
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.
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.
, 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 how kd-tree
s 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,
, and forms a data structure that can be stored efficiently (low space complexity) and that returns the 
-approximate nearest neighbor quickly (low time complexity). In co-authored work with Arya, Netanyahu, Silverman, and Wu, 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. 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 tradeoff
s for approximate nearest neighbor searching, 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
to determine the cell of a subdivision that a query point is in. In, the paper gives an 
time to construct a data structure of 
space that when asked what cell a query point lies in, takes expected time 
where 
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:
) and their main contributions, listed in decreasing order of citations:
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
at The University of Maryland (College Park Campus) whose research is in Computational Geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
.
Biography
David Mount received a B.S. in Computer Science at Purdue UniversityPurdue University
Purdue University, located in West Lafayette, Indiana, U.S., is the flagship university of the six-campus Purdue University system. Purdue was founded on May 6, 1869, as a land-grant university when the Indiana General Assembly, taking advantage of the Morrill Act, accepted a donation of land and...
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
University of Maryland
When the term "University of Maryland" is used without any qualification, it generally refers to the University of Maryland, College Park.University of Maryland may refer to the following:...
in 1984 and is Professor
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
in the department of Computer Science there.
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
His main area of research is Computational GeometryComputational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, which is the branch of algorithms devoted to solving problems of a geometric nature. This field includes problems from classic geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, like the closest pair of points problem
Closest pair of points problem
The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them...
, 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
Nearest neighbor search
Nearest neighbor search , also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q...
, and point location
Point location
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems , motion planning, and computer aided design ....
.
Mount has worked on developing practical algorithms for k-means clustering, a problem known to be NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
. The most common algorithm used is Lloyd's algorithm
Lloyd's algorithm
In computer science and electrical engineering, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm for grouping data points into a given number of categories, used for k-means clustering....
, which is heuristic in nature but performs well in practice. He and others later showed how kd-tree
Kd-tree
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
s 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,
, and forms a data structure that can be stored efficiently (low space complexity) and that returns the -approximate nearest neighbor quickly (low time complexity). In co-authored work with Arya, Netanyahu, Silverman, and Wu, 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. In subsequent work, he investigated the computational complexityComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
of approximate nearest neighbor searching. Together with co-authors Arya and Malamatos, he provided efficient space-time tradeoff
Space-time tradeoff
In computer science, a space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution...
s for approximate nearest neighbor searching, based on a data structure called the AVD (or approximate Voronoi diagram
Voronoi diagram
In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
).
Mount has also worked on point location, which involves preprocessing a planar polygonal subdivision S of size
to determine the cell of a subdivision that a query point is in. In, the paper gives an time to construct a data structure of space that when asked what cell a query point lies in, takes expected time where is the entropyEntropy
Entropy is a thermodynamic property that can be used to determine the energy available for useful work in a thermodynamic process, such as in energy conversion devices, engines, or machines. Such devices can only be driven by convertible energy, and have a theoretical maximum efficiency when...
of the probability distribution of which cells the query points lie in.
In addition to the design and analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
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
Current as of December 8, 2009, here is a list of his most cited works (according to Google ScholarGoogle Scholar
Google Scholar is a freely accessible web search engine that indexes the full text of scholarly literature across an array of publishing formats and disciplines. Released in beta in November 2004, the Google Scholar index includes most peer-reviewed online journals of Europe and America's largest...
) and their main contributions, listed in decreasing order of citations:
- An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions - In this paper they give a n
algorithm (where 
depends on both the number of dimensions 
and the approximate error 
) to find a neighbor that is at most a factor 
distance from the nearest neighbor. - An Efficient k-Means Clustering Algorithm: Analysis and Implementation - In this paper they provide a simpler and more efficient implementation of Lloyd's AlgorithmLloyd's algorithmIn computer science and electrical engineering, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm for grouping data points into a given number of categories, used for k-means clustering....
, which is used in k-means clustering, The algorithm is called the filtering algorithm. - The Discrete Geodesic Problem - 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) polyhedronPolyhedronIn elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
. Their algorithm takes
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 
time. Here, 
is the number of vertices.