David Mount es profesor en el departamento de informática de la Universidad de Maryland, College Park, y su investigación se centra en la geometría computacional .
Mount recibió una licenciatura en Ciencias de la Computación en la Universidad de Purdue en 1977 y obtuvo su doctorado en Ciencias de la Computación en la Universidad de Purdue en 1983 bajo la supervisión de Christoph Hoffmann.
Comenzó a enseñar en la Universidad de Maryland en 1984 y es profesor en el departamento de Ciencias de la Computación allí. [1]
Como docente, ganó el Premio del Decano a la Excelencia en la Enseñanza de la Facultad de Informática, Matemáticas y Ciencias Físicas de la Universidad de Maryland en 2005 y 1997, así como otros premios de enseñanza, incluido el Premio a la Excelencia en la Enseñanza de la Facultad de Ingeniería de Ciencia y Tecnología de Hong Kong en 2001.
El principal campo de investigación de Mounts es la geometría computacional , que es la rama de los algoritmos dedicada a resolver problemas de naturaleza geométrica. Este campo incluye problemas de la geometría clásica , como el problema del par de puntos más cercano , así como problemas aplicados más recientes, como la representación y el modelado informático de curvas y superficies. En particular, Mount ha trabajado en el problema de agrupamiento de k-medias , la búsqueda del vecino más cercano y el problema de la ubicación de puntos .
Mount ha trabajado en el desarrollo de algoritmos prácticos para la agrupación en clústeres de k-medias, un problema conocido por ser NP-hard . El algoritmo más común utilizado es el algoritmo de Lloyd , que es heurístico por naturaleza pero funciona bien en la práctica. Él y otros demostraron más tarde [2] cómo se podían utilizar los árboles kd para acelerar el algoritmo de Lloyd. Han implementado este algoritmo, junto con algunas mejoras adicionales, en la biblioteca de software Kmeans .
Mount ha trabajado en problemas de búsqueda del vecino más cercano y del vecino más cercano aproximado. Al permitir que el algoritmo devuelva una solución aproximada a la consulta del vecino más cercano, se puede obtener una aceleración significativa en la complejidad espacial y temporal. Una clase de algoritmos aproximados toma como entrada la distancia de error, y forma una estructura de datos que se puede almacenar de manera eficiente (baja complejidad espacial) y que devuelve el vecino más cercano aproximado rápidamente (baja complejidad temporal). En un trabajo en coautoría con Arya, Netanyahu , R. Silverman y A. Wu , [3] Mount demostró que el problema del vecino más cercano aproximado se podía resolver de manera eficiente en espacios de baja dimensión. La estructura de datos descrita en ese artículo formó la base de la biblioteca de código abierto ANN para la búsqueda aproximada del vecino más cercano. [4] En un trabajo posterior, investigó la complejidad computacional de la búsqueda aproximada del vecino más cercano. Junto con los coautores Arya y Malamatos, proporcionó compensaciones eficientes de espacio-tiempo para la búsqueda aproximada del vecino más cercano, [5] basándose en una estructura de datos llamada AVD (o diagrama de Voronoi aproximado ).
Mount también ha trabajado en la ubicación de puntos, lo que implica el preprocesamiento de una subdivisión poligonal plana S de tamaño para determinar la celda de una subdivisión en la que se encuentra un punto de consulta. [6] El documento proporciona un tiempo para construir una estructura de datos del espacio que, cuando se pregunta en qué celda se encuentra un punto de consulta, toma el tiempo esperado donde es la entropía de la distribución de probabilidad de en qué celdas se encuentran los puntos de consulta.
Además del diseño y análisis de algoritmos en geometría computacional, Mount ha trabajado en la implementación de algoritmos eficientes en bibliotecas de software como:
Al 8 de diciembre de 2009, a continuación se presenta una lista de sus obras más citadas (según Google Scholar ) y sus principales contribuciones, enumeradas en orden decreciente de citas:
Mount fue nombrado miembro de la clase 2022 de ACM Fellows , "por sus contribuciones a algoritmos y estructuras de datos para el análisis y recuperación de datos geométricos". [8]
