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 problem. 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
k-d 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,
R. Silverman and
A. 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 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 tradeoffs 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 n to determine the cell of a subdivision that a query point is in. 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==