평면상에서 원형의 방해물의 존재시 유클리디안 최단경로 계산 알고리듬

• 영문명: Euclidean Shortest Path with circular obstacles in a plane
• 발행기관: 한국산업경영시스템학회
• 저자명: 유광석 김동욱 조영송 김덕수
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2003년 추계학술대회 논문집, 116~120쪽, 전체 5쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2003.10.01

영문 초록

  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. 배경지식
3. 경로 트리 구성 알고리듬
4. 결론
참고문헌

키워드

Computational Geometry Shortest path Voronoi Diagram optimization