2차원 평면에 원형 장애물들이 주어져 있을 때, 주어진 시작점과 끝점을 잇는 최단 경로를 구하는 문제를 다룬다. 이 때, 원형 장애물들은 서로 교차하지 않으며, 반지름이 각기 다르다고 가정한다. 최단 경로를 효율적으로 구하기 위해서, 본 논문에서는 두 가지의 필터를 제안한다. 첫 번째는 타원 필터이고, 두 번째는 컨벡스-헐 필터이다. 장애물들을 피하면서 주어진 두 점을 연결하는 최단 경로를 구하기 위해서는, 주어진 2차원 공간을 탐색하여야 하는데, 위의 두 필터는 최단 경로와 만나지 않게 되는 원형 장애물들을 미리 걸러냄으로써, 탐색 공간을 효율적으로 줄여준다. 또한 보로노이 다이어그램을 이용하면, 장애물들 간의 인접 정보를 효과적으로 활용할 수 있다. 필터링을 한 후에는 다익스트라 알고리즘을 이용하여 최단 거리를 구한다.

Abstract
 1. 서론
 2. 타원 필터와 컨벡스-헐 필터
 3. 최단 경로 알고리즘
 4. 실험 결과
 5. 결론
 참고문헌

• 박상민(한양대학교 Voronoi Diagram 연구단)
• 김동욱(한양대학교 Voronoi Diagram 연구단)
• Chee Yap(뉴욕 대학교 Courant Institute)
• 김덕수(한양대학교 산업공학과)