원형 장애물 사이에서의 최단 경로 문제

• 영문명: Geodesic problems for circular obstacles
• 발행기관: 한국산업경영시스템학회
• 저자명: 박상민 김동욱 Chee Yap 김덕수
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2005년 춘계학술대회 논문집, 97~100쪽, 전체 4쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2005.05.01

국문 초록

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

목차

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

키워드

최단 경로 원형 장애물 필터 보로노이 다이어그램