Path Optimization Problems in Modest Rectilinear Environment = 실용적인 직각 환경에서의 경로 최적화 문제
저자
발행사항
포항 : 포항공과대학교 일반대학원, 2022
학위논문사항
학위논문(박사)-- 포항공과대학교 일반대학원 : 컴퓨터공학과 2022. 2
발행연도
2022
작성언어
영어
발행국(도시)
경상북도
형태사항
; 26 cm
일반주기명
지도교수: 안희갑
UCI식별코드
I804:47020-200000597903
소장기관
주어진 환경에서 최적의 경로를 찾는 문제는 모든 분야에서 세계적으로 연구되어 오던 중요한 문제이다. 이상적인 평면에선 출발지에서 도착지로 직진을 하는 것이 대부분의 기준에서 최적의 경로이기 때문에, 단순히 거리와 경로를 구하는 문제를 뛰어넘어 보로노이 다이어그램(Voronoi diagram), 중심점 찾기 문제 등 최적 경로에서 파생되는 다양한 기하 문제들에 대해 최적의 연구 결과가 존재한다.
하지만 현실 세계는 이상적인 평면이 아니며, 보다 다양한 물체들이 변수로 작용한다. 이러한 장애물이 있는 환경을 평면 상에서의 다각 환경(polygonal domain)으로 치환할 수 있으며, 다각 환경에서의 최적의 경로를 찾는 문제와 파생 기하 문제들 또한 활발한 연구 주제 중 하나이다. 하지만, 다각 환경에서의 최적의 경로를 찾는 대부분의 알고리즘이 지닌 문제점은 복잡하여 구현상의 어려움이 있다는 것이다. 따라서 경로를 구성하거나 물체들을 이루는 요소가 축에 평행한 직각 환경에서의 최적의 경로를 찾는 문제들도 활발하게 연구되고 있다.
본 학위논문에서는 실용적인 직각 환경에서의 최적의 경로 문제 3가지에 대해 효율적인 알고리즘을 제시한다.
첫번째, 장애물이면서 동시에 질의의 대상이 되는 $n$개의 직사각형이 있을 때, 다양한 경로 최적화 문제들을 해결하는 자료구조를 제시했다. 기존 연구의 대부분은 대상이 점인 경우 최단 경로를 구하는 문제에 국한되어 있는데, 이를 좀 더 일반화시킨 연구를 진행하였다. O(n^2) 전처리 시간과 공간을 소요하여 O(log n) 질의 시간으로 최단 경로를 계산할 수 있는 자료구조를 고안하였다. 또한, 위 자료구조를 활용하여, 가장 가깝거나 가장 먼 직사각형을 구하는 자료구조 또한 제시하였다. n개의 직사각형 장애물이 주어졌을 때, 직사각형 장애물들이 만드는 환경의 지름과 중심점을 O(n^2 log n) 시간만에 구하는 알고리즘 또한 제시하였다.
두번째, 복잡도가 N인 두 개의 직각 다각형과 장애물로 취급되는 직각 다각형들이 상호 박스-분리(box-disjoint)된 복잡도 n인 환경에서 최소-선분 최단 경로(Minimum-link shortest path)를 구하는 효율적인 알고리즘을 제시했다. 기존 연구에서 제시되었던 일반적인 직각환경에서의 O(n + h log 3/2 h) 시간 및 O(n + h log h) 공간 알고리즘보다 실용적인 박스-분리 환경에서 최소-선분 최단 경로를 구해야 하는 두 개체를 좀 더 일반화시켜서 O((N+n) log (N+n)) 시간과 O(N+n) 공간만을 사용하는 알고리즘을 개발하였다.
마지막으로, 사각형 장애물의 개수가 n이고, 점의 개수가 m인 환경에서 최적의 시간과 공간 복잡도를 가지는 최원격 이웃 탐색 자료구조를 제시했다. 기존 연구에서 제시되었던 O(nm log (n+m)) 전처리 시간과 O(nm) 공간을 소요하여 O(log (n+m)) 질의 시간을 가지는 자료구조에서 전처리 시간을 O(nm + n log n + m log m) 시간으로 향상시킨 새로운 최적의 자료구조를 제시하였다. 위 자료구조를 이용하여, 같은 시간과 공간만을 사용하여 정확한 최원격 보로노이 다이어그램과 중심점을 구하는 알고리즘을 제시하였다. 이 결과는 장애물이 분리되어 존재하는 평면 상의 모든 환경에서 정확한 최원격 보로노이 다이어그램을 구한 최초의 최적 알고리즘이다.
The problem to find optimal paths for a given environment is one of world-wide famous problems in fields related to optimization. For a plane with no restriction, the straight line segment between two objects is the optimal path in most standards, and it takes constant time to compute such optimal path. Using this fact, beyond computing paths or distances, many optimization problems and algorithms in the plane has been studied extensively, such as Voronoi diagrams, the diameter and center, and so on.
However, the real world is hard to apply to the ideal plane, since various objects of the real world act as obstacles. A plane with such obstacles can be regarded as a polygonal domain. Optimization problems in a polygonal domain are also fundamental problems in computational geometry, so there are many results of path optimizations in general polygonal domain. Along with the problems in the polygonal domain, path optimization problems in a rectilinear environment, which is more practical and applicable than a polygonal domain, are studied actively.
In this thesis, we study three kinds of path optimization problems in the modest rectilinear environment
and present efficient algorithms for the problems.
First, given a set of open axis-aligned disjoint rectangles, each of which plays as both an obstacle and a target, we seek to find shortest obstacle-avoiding rectilinear paths from a query to the nearest target and the farthest target. The distance to a target is determined by the point on the target achieving the minimum or maximum geodesic distance among all points on the boundary of the target. We show how to construct data structures supporting such shortest path queries to the nearest and farthest neighbors efficiently.
Second, we compute shortest paths connecting two axis-aligned rectilinear simple polygons in the domain consisting of axis-aligned rectilinear obstacles in the plane. The bounding boxes, one defined for each polygon and one defined for each obstacle, are disjoint. We present an algorithm that computes a minimum-link rectilinear shortest path connecting the two polygons and avoiding the obstacles.
Third, we present an algorithm to compute the geodesic L1 farthest-point Voronoi diagram of m point sites
in the presence of n rectangular obstacles in the plane. This result is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query.
서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)