Дэвид Маунт - Википедия - David Mount

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

биография

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

Он начал преподавать в Университет Мэриленда в 1984 году и является Профессор на кафедре информатики есть.^[1]

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

Исследование

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

Маунт работал над разработкой практических алгоритмов для кластеризации k-средних, известной как проблема NP-жесткий. Чаще всего используется алгоритм Алгоритм Ллойда, который является эвристическим по своей природе, но хорошо работает на практике. Он и другие позже показали ^[2] как k-d деревья может использоваться для ускорения алгоритма Ллойда. Они реализовали этот алгоритм вместе с некоторыми дополнительными улучшениями в библиотеке программного обеспечения. Kmeans.

Маунт работал над проблемами поиска ближайшего соседа и приблизительного ближайшего соседа. Позволяя алгоритму возвращать приблизительное решение для запроса ближайшего соседа, можно получить значительное ускорение пространственной и временной сложности. Один класс приближенных алгоритмов принимает в качестве входных данных расстояние ошибки, ${ displaystyle epsilon}$, и формирует структуру данных, которую можно эффективно хранить (низкая сложность пространства) и которая возвращает ${ displaystyle (1+ epsilon)}$-приблизительный ближайший сосед быстро (низкая временная сложность). В соавторстве с Арьей, Нетаньяху, Р. Сильверман и А. Ву,^[3] Маунт показал, что проблема приближенного ближайшего соседа может быть эффективно решена в пространствах низкой размерности. Структура данных, описанная в этой статье, легла в основу библиотеки с открытым исходным кодом ИНС для приблизительного поиска ближайшего соседа.^[4] В последующей работе он исследовал вычислительная сложность приблизительного поиска ближайшего соседа. Вместе с соавторами Арьей и Маламатосом он обеспечил эффективное пространственно-временные компромиссы для приблизительного поиска ближайшего соседа,^[5] на основе структуры данных, называемой AVD (или приблизительный Диаграмма Вороного ).

Mount также работал с местоположением точки, что включает предварительную обработку планарно-полигональное деление S размера ${ displaystyle n}$ для определения ячейки подразделения, в котором находится точка запроса.^[6] В статье дается ${ displaystyle O (nlogn)}$ время построить структуру данных ${ Displaystyle О (п)}$ пространство, которое на вопрос, в какой ячейке находится точка запроса, занимает ожидаемое время ${ Displaystyle Н + О ({ sqrt {H}} + 1)}$ куда ${ displaystyle H}$ это энтропия распределения вероятностей, в каких ячейках находятся точки запроса.

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

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

Наиболее цитируемые работы

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

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

Рекомендации

внешняя ссылка

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