데이비드 마운트

데이비드 마운트는 메릴랜드 대학의 컴퓨터 과학과 교수로 컴퓨터 기하학에 관한 연구를 하고 있다.

전기

마운트는 1977년 퍼듀 대학의 컴퓨터 과학에서 B.S.를 받았고 1983년 크리스토프 호프만의 조언으로 퍼듀 대학의 컴퓨터 과학에서 박사학위를 받았다.

그는 1984년에 메릴랜드 대학에서 가르치기 시작했고 그곳의 컴퓨터 과학과의 교수다.^[1]

교사로서 그는 2005년과 1997년에 메릴랜드 대학교, 컴퓨터 수학과 물리과학대학 학장상을 수상했으며, 2001년에는 홍콩 과학 기술, 공대 교수상 등 다른 교수상을 수상했다.

리서치

마운츠의 주요 연구 분야는 컴퓨터 기하학으로, 기하학적 성질의 문제 해결에 전념하는 알고리즘의 분기다.이 필드에는 가장 가까운 점 쌍 문제와 같은 고전 기하학의 문제뿐만 아니라 컴퓨터 표현 및 곡선과 표면의 모델링과 같은 보다 최근에 적용된 문제가 포함된다.특히 마운트는 k-평균 군집화 문제, 가장 가까운 이웃 찾기, 지점 위치 등에 공을 들였다.

마운트는 NP-hard로 알려진 문제인 k-means 클러스터링을 위한 실제 알고리즘 개발에 힘써왔다.가장 많이 사용되는 알고리즘은 자연에서는 휴리스틱하지만 실제로는 잘 작동하는 로이드 알고리즘이다.그와 다른 사람들은 나중에 어떻게 k-d 트리가 로이드의 알고리즘을 가속화하는 데 사용될 수 있는지를 보여주었다.그들은 소프트웨어 라이브러리 Kmeans에 이 알고리즘을 몇 가지 추가적인 개선과 함께 구현했다.

마운트는 가장 가까운 이웃과 거의 가장 가까운 이웃의 수색 문제를 해결했다.알고리즘이 가장 가까운 인접 쿼리에 근사 솔루션을 반환할 수 있게 함으로써 공간과 시간의 상당한 속도를 높일 수 있다.한 클래스의 근사 알고리즘은 오류 거리인 $ϵ{\displaystyle }${\$displaystyle \epsilon$}을 입력하여 효율적으로 저장할 수 있는 데이터 구조를 형성하며(저공간 복잡성${\displaystyle ),}$가장 가까운 이웃인$$ $({\displaystyle 1}$+\$displaystyle (1+\epsilon )}$을(저시간 복잡성)으로 빠르게 반환한다.아리아, 네타냐후, R. 실버만, A와 공동 저술한 작품. Wu,^[3] Mount는 대략 가장 가까운 이웃 문제가 낮은 차원의 공간에서 효율적으로 해결될 수 있다는 것을 보여주었다.이 논문에서 설명한 데이터 구조는 근접한 인접 검색에 대한 ANN 오픈 소스 라이브러리의 기초를 형성하였다.^[4]후속 작업에서, 그는 대략 가장 가까운 이웃을 찾는 계산상의 복잡성을 조사했다.공동저자인 아리아, 말라마토스와 함께, 그는 AVD(또는 대략적인 보로노이 도표)라고 불리는 데이터 구조에 기초하여 ^[5]근접한 이웃을 찾기 위한 효율적인 공간-시간 절충을 제공했다.

Mount는 또한 지점 위치에 대한 작업을 수행했는데, $여기$에는 쿼리 지점이 있는 부분군의 셀을 결정하기 위해$$ 크기가 n$${\$displaystyle n}$인 평면 다각형 부분 S를 사전 처리하는 작업이 포함된다.^[6]The paper gives an ${\displaystyle O(nlogn)}$ time to construct a data structure of ${\displaystyle O(n)}$ space that when asked what cell a query point lies in, takes expected time ${\displaystyle H+O({\sqrt {H}}+1)}$ where ${\displaystyle H}$ is the entropy of the probability쿼리 포인트가 있는 셀의 분포.

Mount는 연산 기하학에서 알고리즘의 설계와 분석 이외에도 다음과 같은 소프트웨어 라이브러리에서 효율적인 알고리즘의 구현에 힘써 왔다.

• ANN - 근접한 인접 검색
• ISODATA - 널리 사용되는 클러스터링 알고리즘의 효율적인 구현
• KMeans - k-평균 군집화

가장 많이 인용된 작품

2009년 12월 8일 현재 그가 가장 많이 인용한 작품 목록(Google Scholar에 따르면)과 이들의 주요 공헌 목록(인용 순서가 감소함)은 다음과 같다.

1. 최적 알고리즘 근사에 Nearest 이웃 찾고 있어 고정 Dimensions[3]에-cd, ϵ{\displaystyle c_{d,\epsilon}}치수 d{\displaystyle d}의 대수와 그 approxi에 따라 이 논문에서 그들은(오빠 O(cd,ϵ 로그 ⁡(n)){\displaystyle O(c_{d,\epsilon}\log(n))}알고리즘을 준다.매트.e 가장 가까운 이웃으로부터 최대 ${\displaystyle 1}$+ ${\displaystyle ϵ}$) {\$displaystyle$ (1$+\epsilon )}$ 거리에$$ 있는 이웃을 찾기 위한 오류 $ϵ{\displaystyle }$ ${\$$displaystyle \epsilon$ $\}.$
2. 효율적인 k-평균 군집화 알고리즘: 분석과 구현^[2] - 본 논문에서 k-평균 군집화에 사용되는 로이드 알고리즘을 보다 단순하고 효율적으로 구현하는 방법을 제공한다.이 알고리즘은 필터링 알고리즘이라고 불린다.
3. 이산 지오데틱 문제[7]-이 논문에서 그들은 주어진(아마도 비콘벡스)다면체의 표면 위를 이동해야 하는 제약을 받는 선원에서 목적지까지의 최단 경로를 계산한다.이들의 알고리즘은 첫 번째 대상에 대한 첫 번째 최단 경로를 찾는 데 $O{\displaystyle ({n\mathrm{}}^{}}$ 2 ${\displaystyle \log }$⁡ ${\displaystyle (n}$ ${\displaystyle$ O$(n^{2}\log(n)}$ 시간이$$ 소요되며 (동일한 소스에서) 추가 대상에 대한 최단 경로를 $O{\displaystyle (\log \mathrm{nn}}$ )${\displaystyle O(\log$ n$)}$ 시간으로$$ 계산할 수 있다.$여기$서 n ${\displaystyle n}$은 정점의 수입니다.

참조

외부 링크

• 공식 웹사이트
• 데이터 구조 및 알고리즘(C++)