Дэвид Маунт

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

Биография [ править ]

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

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

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

Исследование [ править ]

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

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

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

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

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

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

Наиболее цитируемые работы [ править ]

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

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

Ссылки [ править ]

Внешние ссылки [ править ]

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