Path Optimization Problems in Modest Rectilinear Environment

Abstract

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.

주어진 환경에서 최적의 경로를 찾는 문제는 모든 분야에서 세계적으로 연구되어 오던 중요한 문제이다. 이상적인 평면에선 출발지에서 도착지로 직진을 하는 것이 대부분의 기준에서 최적의 경로이기 때문에, 단순히 거리와 경로를 구하는 문제를 뛰어넘어 보로노이 다이어그램(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) 시간으로 향상시킨 새로운 최적의 자료구조를 제시하였다. 위 자료구조를 이용하여, 같은 시간과 공간만을 사용하여 정확한 최원격 보로노이 다이어그램과 중심점을 구하는 알고리즘을 제시하였다. 이 결과는 장애물이 분리되어 존재하는 평면 상의 모든 환경에서 정확한 최원격 보로노이 다이어그램을 구한 최초의 최적 알고리즘이다.