We propose a new algorithm for a classical problem in the planer computational geometry: computing a shortest path between two points in the presence of circular obstacles. Proposed algorithm actually computes a path tree that encodes a shortest path between given two points. Types of path are defined as a tangent line segment between circles, between point and circle, or as an arc. Using circle set voronoi diagram, geometric information that is very useful to search circles is obtained. The key of proposed algorithm is the reduction of the number of circles to need for constructing path tree. The main advantages of our algorithm are its robustness, speed, and the simplicity in implementation.

Abstract
 1. 서 론
 2. 배경지식
  2.1 Visibility graph method
  2.2 원집합의 보로노이 다이어그램
 3. 경로 트리 구성 알고리듬
  3.1 단위 경로
  3.2 경로 트리 구성 알고리듬
 4. 결 론
 참고문헌

• 유광석(한양대학교 산업공학과)
• 김동욱(한양대학교 산업공학과)
• 조영송(Voronoi Diagram 연구단)
• 김덕수(한양대학교 산업공학과)