Дэвид Маунт

Эта статья об американском ученом-компьютерщике. Чтобы узнать об английском барабанщике глэм-рока, см. Mud (группа) .

Дэвид Маунт
Национальность	Американский
Альма-матер	Университет Пердью
Известный	Вычислительная геометрия
Научная карьера
Поля	Информатика
Учреждения	Университет Мэриленда, Колледж-Парк
Докторантура	Кристоф Хоффманн
Веб-сайт	www .cs .umd .edu /пользователи /устанавливать /

Дэвид Маунт — профессор области вычислительной факультета информатики Университета Мэриленда в Колледж-Парке, чьи исследования находятся в геометрии .

Биография

Маунт получил степень бакалавра компьютерных наук в Университете Пердью в 1977 году и докторскую степень. Степень бакалавра компьютерных наук в Университете Пердью в 1983 году под руководством Кристофа Хоффмана.

Он начал преподавать в Университете Мэриленда в 1984 году и является там профессором кафедры компьютерных наук.

Как преподаватель, он выиграл Премию декана Колледжа компьютерных, математических и физических наук Университета Мэриленда за выдающиеся достижения в преподавании в 2005 и 1997 годах, а также другие награды в области преподавания, включая премию Гонконгской школы науки и технологий и Инженерной школы за выдающиеся достижения в преподавании. Благодарность в 2001 году.

Исследовать

Основная область исследований Маунтса — вычислительная геометрия , раздел алгоритмов, посвященный решению задач геометрической природы. Эта область включает в себя проблемы классической геометрии , такие как задача о ближайшей паре точек , а также более поздние прикладные проблемы, такие как компьютерное представление и моделирование кривых и поверхностей. В частности, Маунт работал над проблемой кластеризации k-средних , поиском ближайшего соседа и проблемой местоположения точки .

Маунт работал над разработкой практических алгоритмов кластеризации k-средних — проблемы, известной как NP-трудная . Наиболее распространенным используемым алгоритмом является алгоритм Ллойда , который является эвристическим по своей природе, но хорошо работает на практике. Позже он и другие показали как деревья kd можно использовать для ускорения алгоритма Ллойда. Они реализовали этот алгоритм вместе с некоторыми дополнительными улучшениями в программной библиотеке Kmeans .

Маунт работал над задачами поиска ближайшего соседа и приближенного ближайшего соседа. Позволив алгоритму возвращать приближенное решение запроса ближайшего соседа, можно получить значительное ускорение в пространственной и временной сложности. Один класс приближенных алгоритмов принимает на вход расстояние до ошибки: $\epsilon$и формирует структуру данных, которую можно эффективно хранить (малая сложность пространства) и которая возвращает $(1+\epsilon )$- Быстрое приближение ближайшего соседа (низкая временная сложность). В соавторстве с Арьей, Нетаньяху , Р. Сильверманом и А. Ву , Маунт показал, что приближенная задача о ближайшем соседе может быть эффективно решена в пространствах низкой размерности. Структура данных, описанная в этой статье, легла в основу библиотеки с открытым исходным кодом ANN для приблизительного поиска ближайшего соседа. В последующей работе он исследовал вычислительную сложность приблизительного поиска ближайшего соседа. Вместе с соавторами Арьей и Маламатосом он предложил эффективные пространственно-временные компромиссы для приблизительного поиска ближайшего соседа. на основе структуры данных, называемой AVD (или приближенной диаграммой Вороного ).

Маунт также работал над расположением точек, что включает предварительную обработку плоского многоугольного подразделения S размером $n$ для определения ячейки подразделения, в которой находится точка запроса. В статье дается $O(nlogn)$ время построить структуру данных $O(n)$ пространство, которое на вопрос, в какой ячейке находится точка запроса, занимает ожидаемое время $H+O({\sqrt {H}}+1)$ где $H$ — энтропия распределения вероятностей, в которых лежат точки запроса.

Помимо разработки и анализа алгоритмов вычислительной геометрии, Маунт работал над реализацией эффективных алгоритмов в библиотеках программного обеспечения, таких как:

• ANN — приблизительный поиск ближайшего соседа
• ISODATA — эффективная реализация популярного алгоритма кластеризации
• KMeans — кластеризация k-средних

Самые цитируемые работы

По состоянию на 8 декабря 2009 г. приведен список его наиболее цитируемых работ (по данным Google Scholar ) и их основных вкладов, перечисленных в порядке убывания цитирования:

1. Оптимальный алгоритм приближенного поиска ближайших соседей в фиксированных измерениях - В этой статье они дают $O(c_{d,\epsilon }\log(n))$ алгоритм (где $c_{d,\epsilon }$ зависит как от количества измерений $d$ и приблизительная погрешность $\epsilon$) найти соседа, который является не более чем фактором $(1+\epsilon )$ расстояние от ближайшего соседа.
2. Эффективный алгоритм кластеризации k-средних: анализ и реализация — В этой статье они предоставляют более простую и эффективную реализацию алгоритма Ллойда , который используется при кластеризации k-средних . Алгоритм называется алгоритмом фильтрации.
3. Дискретная геодезическая задача - В этой статье они вычисляют кратчайший путь от источника к пункту назначения, ограниченный необходимостью путешествовать по поверхности заданного (возможно, невыпуклого ) многогранника . Их алгоритм занимает $O(n^{2}\log(n))$ время нахождения первого кратчайшего пути к первому пункту назначения и кратчайший путь к любому дополнительному пункту назначения (из того же источника) можно вычислить в $O(\log n)$ время. Здесь, $n$ это количество вершин.

Признание

Маунт был включен в список стипендиатов ACM 2022 года «за вклад в разработку алгоритмов и структур данных для анализа и извлечения геометрических данных».

Внешние ссылки

• Официальный сайт
• Структуры данных и алгоритмы в C++
• Google Академика