• >
  • 스타랩과제
  • >    기하알고리즘 연구실
기하알고리즘 연구실
동적 기하환경에서의 최적의 자료 구조 및 응용 알고리즘
포항공과대학교 / 총괄 책임자 : 안희갑 / http://tcs.postech.ac.kr/
과제 소개
본 연구는 공간에 존재하는 물체 등의 데이터를 다루는 최적의 알고리즘 설계 기술을 개발하는 것을 목표로 한다. 그 중에서도 공간의 구성 물체와 데이터가 시시각각 동적으로 변화하는 환경에서 빠른 시간 내에 최단 경로와 기하자료구조를 계산하는 최적의 기하 알고리즘을 설계하는 연구를 진행하고 있다.
인사말
컴퓨터 알고리즘은 컴퓨터 소프트웨어의 발전을 이끌어 온 핵심 기술입니다. 그 중에서도 기하 알고리즘은 우리가 생활하고 있는 다양한 환경에 존재하는 물체를 대상으로 여러 가지 계산을 수행하는 연구로, 물체 간 최단 거리, 클러스터링, 매칭 등 물체 분석과 분류, 계산에서 핵심이 되는 기술입니다. 대부분의 컴퓨터 알고리즘은 공간과 데이터가 정적인 환경에서 효율적으로 계산하기 위한 구조로 설계되었기 때문에 기하 환경이 변할 경우 이를 효율적으로 반영하지 못하는 한계가 있습니다. 저희 연구팀은 이론과 원리를 기반으로 하는 면밀한 분석을 통해, 동적 환경에서도 효율적으로 동작하는 최적의 자료구조와 알고리즘을 설계하는 것을 목표로 하고 있습니다. 장기적으로는 이러한 실생활의 어려운 문제들을 해결하는 효율적 알고리즘을 설계하고 구현할 수 있는 능력을 가진 우수한 인력 양성에 초점을 두고 있습니다.
연락처
전화 : 054)279-1478
메일주소 : heekap@postech.ac.kr
찾아오는길
경상북도 포항시 남구 청암로 77 포항공과대학교 공학 2동 306호
고속버스
- 경유지정보 : 서울, 대전, 마산, 광주 방면에서 고속버스 이용 → 포항도착
- 고속버스 이용 및 예약문의 : 1588-6900 ( http://www.kobus.co.kr )
- 교통편 : 택시이용시 20분 소요
시외버스
- 경유지정보 : 대구, 경북, 강원, 부산, 경남, 전남, 경기, 충청지역 시외버스 이용 → 포항도착
- 시외버스 이용 및 예약문의 : 1666-2313 ( http://www.포항터미날.kr )
- 교통편 : 택시 이용시 15분 소요
자가
- 서울 출발시
1. 경부고속도로 → 대구 → 포항고속도로 → 포항IC → 이동도로 → 이동사거리 → 신단지교차로 → POSTECH → C5
2. 경부고속도로 → 대구 → 포항고속도로 → 포항IC → 경주방향 → 유금IC → 유강터널 → POSTECH → C5
- 대구 출발시
1. 대구 → 포항고속도로 → 포항IC → 이동도로 → 이동사거리 → 신단지교차로 → POSTECH → C5
2. 대구 → 포항고속도로 → 포항IC → 경주방향 → 유금IC → 유강터널 → POSTECH → C5
- 부산 출발시 : 경부고속도로 → 경주IC → 포항방향 → 유강터널→ POSTECH → C5
총괄책임자
  • 총괄 책임자: 안희갑
  • 고차원 환경에서 동작하는 알고리즘 연구 및 총괄
  • 054)279-1478 (office)
  • heekap@postech.ac.kr
  • sungeui 'at' gmail.com
안희갑 교수는 포항공과대학교 컴퓨터공학과에 재직중이며, 기하 알고리즘 연구실(SW 스타랩)을 이끌고 있다. 주요 연구 분야는 알고리즘, 기하 알고리즘, 자료 구조에 대한 설계와 분석 등이며, 동적 환경에서의 기하 최적화 문제 해결과 컴퓨터 비전 및 머신 러닝 알고리즘의 효율적인 설계와 개발에 주력하고 있다. 기하 알고리즘 분야의 최우수 국제 학술대회인 SoCG를 비롯하여 컴퓨터 알고리즘의 주요 국제 학술대회와 국제 저널에 논문을 발표하고 있으며, 국제 학술대회의 프로그램 위원장 및 위원으로 활동하고 있다. 컴퓨터 비전 및 인공지능에도 연구 관심이 많으며 NIPS, CVPR, AAAI 등 권위있는 국제 학술대회에 논문을 발표하였다. 컴퓨터 알고리즘 분야의 국제 저널에 편집위원으로 활동하고 있으며, 2017년에는 일본 NII Shonan Meeting과 Aslla 심포지엄의 조직위원장을 역임하였으며, 아시아 알고리즘 협회인 AAAC의 창립이사로 활동하고 있다.
구성원
이름 연구분야 메일
김민철 소프트웨어 개발 내역 검증 및 센터 문제 연구 rucatia@postech.ac.kr
김성환 라이브러리 및 API 개발 uneasiness@postech.ac.kr
안태훈 라이브러리 및 이동 경로 탐색 알고리즘 SW 개발 sloth@postech.ac.kr
여진영 동적 데이터 처리 자료구조 연구 및 설계 jinyeo@postech.ac.kr
이승준(석) 클러스터링 연구 및 홈페이지 관리 sjoonlee@postech.ac.kr
이승준(박) 고차원 데이터 복잡도 연구 juny2400@postech.ac.kr
이재서 SW 테스팅 방법론 및 알고리즘 연구 sean96@postech.ac.kr
이지아 SW 라이브러리 결점 확인 및 검증 cee5539@postech.ac.kr
최종민 Github 관리 및 최 근접 이웃 탐색 알고리즘 SW 개발 icothos@postech.ac.kr
이다영 다각형 환경에서의 최단 경로 쿼리 알고리즘 연구 및 개발 dayoung@postech.ac.kr
연구목표
본 연구의 목표는 동적 기하 환경에서의 문제들을 효율적으로 해결할 수 있는 자료구조 및 알고리즘을 개발하고, 이를 실제로 구현하여 집대성한 오픈소스 SW 라이브러리를 개발하는 것이다. 대표적으로, 최 근접 이웃 탐색(NNS) 문제는 공간에 주어진 데이터들 가운데 질의에 가장 가까운 데이터를 찾는 것이 목표이다. 이를 해결하는 방법은 선형 탐색, 공간 분할, 저 차원 변환 등이 있으나 주어진 공간이 동적으로 변화하는 것에 대응하지 못한다. 동적 환경의 NNS 문제를 지원하는 자료구조 및 알고리즘 뿐 아니라, 최단 경로나 중심점 탐색 등의 여러 기하 문제에 대해서 알고리즘을 연구 개발하고 궁극적인 목표이다.
연구내용
2차원 동적 환경에서의 NNS 문제를 지원하는 자료구조 개발)
데이터는 하나의 점으로 표시될 수 있고, 이 점이 가진 정보의 개수는 차원으로 표시될 수 있다. 소위 차원의 저주(The curse of dimensionality)에 의해서 차원만큼의 시간이 배로 소요된다. 우선 2차원에서의 점으로 표현되는 데이터와 선분으로 표현되는 물체에 대해 이들이 동적으로 변화할 수 있는 NNS 문제를 해결하는 자료구조와 알고리즘을 개발한다. 동적 공간에서 위치 질의를 지원하는 자료구조를 논문으로 발표하였고, 이외에 문제를 해결하기 위해 필요한 다양한 부 문제 및 자료구조를 연구 중에 있다.
Shortest Path Map 개발
단순한 2차원 평면 상에서, 한 점에서 시작하여 다른 평면 위에 모든 점으로 가는 최단 거리는 유클리드 직선 거리이다. 하지만 장애물이 존재한다면, 최단 거리는 여러 선분으로 나타날 수 있다. 이 때 공간을 최단 거리의 조합적 구조가 동일한 점들이 같은 지역에 속하도록 분할할 수 있는데, 이 분할을 Shortest Path Map이라고 한다. 이는 O(n logn)의 시간복잡도로 해결할 수 있다고 알려져 있으나, 구현되어 있는 오픈소스 SW는 없다. 기하 알고리즘의 많은 문제에 이용되는 근본적인 자료구조로, 현재 개발 중에 있다.
최우수 학술대회 성과
- 최우수 학술대회 성과
- 동적 공간에서의 위치 질의 알고리즘 및 자료구조 제시 (세계 최고)
- 점 집합의 Clustering 범위 질의의 효율적 자료구조 제시
- 최 근접 이웃 질의를 처리하는 Quantized 이동 알고리즘 제시(PQT)
우수 학술대회 성과
- 단순 다각형 내부의 최단거리 자료구조의 시간 및 공간 Tradeoff 연구
- 다각형 내부에서 Visibility를 위한 최단시간 이동 경로 알고리즘 연구
- 우선순위 기반의 점 집합 최 근접 이웃 탐색 알고리즘 연구 및 개발
공개 SW 라이브러리
- https://github.com/icothos/dnn (개발 중)
- Growing Disk, Compressed Quad-tree 등
인력 양성 성과
박사 4명 졸업, 학사 2명 졸업
학술계 진출: 1명 (오은진)
- 독일 소재의 Max Planck Institute for Infomatics에 Post Doctor로 진출
- 동적 공간분할 연구 및 컴퓨터 알고리즘분야 세계 최우수 국제학술대회 논문 6편
- Lise Meitner Award Fellowship 수상
산업체 취업: 4명 (삼성 디스플레이, NAVER 등)
대학원 진학: 1명 (포항공과대학교 대학원)
홍보 홈페이지
연구실 홈페이지
http://tcs.postech.ac.kr
DNN 라이브러리 홈페이지 (개발 중)
http://dnn.postech.ac.kr/