직사각형 장애물을 피하는 선분 최단경로 (Shortest Paths Between Line Segments in the Presence of Rectangular Obstacles)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 / 50권 / 3호 / 204 ~ 209페이지
· 저자명 : 서찬양, 안태훈, 안희갑

초록

본 논문에서는 평면 상에 주어진 n개의 좌표축에 평행한 직사각형 장애물들과 두 개의 좌표축에 평행한 선분에 대해, 장애물을 피하는 두 선분 사이의 L1최단경로를 계산하는 문제를 다룬다. 두 선분 사이의 경로는 각 선분에서 점을 한 개씩 택할 때, 선택된 두 점 사이의 최단경로로 정의된다. 점의 선택 기준에 따라 두 선분 사이의 경로는 다양하게 정의될 수 있다. 우리는 그 중 최단경로의 길이가 최소가 되는 최소 최단경로와, 길이가 최대가 되는 최대 최단경로를 구하는 알고리즘을 제시한다. 본 논문에서는 최소 최단경로를 O(nlogn) 시간에 계산하는 알고리즘과 최대 최단경로를 O(n2) 시간에 계산하는 알고리즘을 제시한다.

영어초록

In this paper, we present an algorithm computing L1 shortest paths between two line segments in the presence of rectangular obstacles. A path between two line segments is the shortest path between two selected points from each line segment. The selected points vary by the definition of a path between the line segments. Among them, we consider minimum shortest path which is defined by the points that minimize the length and maximum shortest path which is defined by the points that maximize the length. We present an O(nlogn)-time algorithm computing minimum shortest path and an O(n2)-time algorithm computing maximum shortest path.

참고자료

· 없음