This thesis addresses discretization of geometric cover problems in the plane with translation and rotation of planar objects, and incorporates its applications to a sensor placement problem and a pulse scheduling problem in radar resource management.
For a given set $P$ of $n$ points in the plane and a compact planar object $T_0$, the generalized geometric cover problem is to find a minimum cardinality collection of planar transforms of $T_0$ such that the union of the transforms in the collection contains all the points in $P$. Two particular cases of the generalized geometric cover problem are considered in this thesis: `the geometric cover problem' including only translation of planar objects; and `the geometric cover problem with rotation' including rigid transformation, i.e.\ translation combined with rotation of planar objects. It is shown that the infinite continuous solution spaces in the plane of the geometric cover problems can be discretized into reduced finite solution spaces consisting of so-called distinct canonical transforms, and thus the geometric cover problems can be converted to the geometric set cover problem, of which solution space is a given finite-size collection of transforms.
For the geometric cover problem with only translation, a planar structure called point inversion graph is presented that identifies the locations of distinct canonical translates, and some polynomial discretization algorithms are proposed to find the reduced finite solution space for disks, convex/non-convex polygons (including holes), and planar objects consisting of finite Jordan curves. It is shown that the collection of all distinct canonical translates of the geometric cover problems for all rotation angles includes all of distinct canonical transforms for the geometric cover problem with rotation. Hence, in the geometric cover problem with rotation for convex polygons, a discretization algorithm is devised to construct the finite solution space by tracing the changes of the point inversion graph with a sweeping plane in the rotation space of the problem. The asymptotic time complexities of the presented algorithms for both geometric cover problems are analyzed.
The discretization algorithms are utilized in two practical applications: a) the minimum sensor cover problem of a distributed multi-sensor system; b) interleaved pulse scheduling for multiple target tracking in pulse Doppler phased array radars with subarray level digital beamforming. The continuous problem domains of both problems cause principal difficulties in the exact formulation of the problems and the computation of optimal solutions. Thus, the solution space of each problem is discretized and then the problem is formulated as a combinatorial optimization problem.
Heuristic algorithms are proposed as computationally tractable solution methods for the problems, and compared with the optimal solutions by numerical simulations.
본 논문은 평면 도형의 평행 이동과 회전을 포함하는 기하 덮개 문제의 이산화에 대해 다룬다. 또한 센서 배치 문제와 레이더 자원 관리에서의 펄스 스케줄링 문제에 이산화 기법을 응용한 결과를 포함하고 있다.
평면상에 주어진 $n$개의 점의 집합 $P$와 평면 도형 $T_0$에 대하여, $T_0$의 평면 변환 도형들로 이루어진 집합이 $P$의 점을 모두 포함할 때, 그러한 집합 중에서 최소의 집합을 찾는 문제를 ‘일반화된 기하 덮개 문제’로 정의한다. 본 논문에서는 평면 변환의 종류에 따라 일반화된 기하 덮개 문제를 한정시켜서, 평면 도형의 평행 이동만을 고려한 ‘기하 덮개 문제’와 평행 이동과 평면상의 회전을 포함하는 ‘회전 기하 덮개 문제’를 고려하였다. 먼저, 이 기하 덮개 문제들의 무한하고 연속적인 해 공간은 축소된 유한 해 공간으로 이산화될 수 있으며, 축소된 유한 해 공간은 서로 다른 정준 변환 도형으로 구성되어 있다는 것을 증명하였다. 이에 따라 기하 덮개 문제들은 미리 주어진 유한한 개수의 도형들로 해 공간이 구성되어 있는 기하 집합 덮개 문제로 환원시켜 해결할 수 있음을 보였다.
또한 두 기하 덮개 문제들의 이산화를 수행하는 알고리듬들을 개발하고 그 점근적 수행시간을 분석하였다. 평행 이동만을 고려한 기하 덮개 문제에서 서로 다른 정준 변환 도형들을 효율적으로 찾기 위해 ‘점대칭 그래프’라는 평면 구조를 고안하였으며, 원반, 볼록/오목 다각형 또는 유한한 수의 Jordan 곡선으로 구성된 다양한 유형의 평면 도형들에 대하여 기하 덮개 문제를 이산화하는 알고리듬들을 제시하였다. 한편, 주어진 평면 도형 $T_0$를 회전시키는 모든 각도에서의 기하 덮개 문제의 정준 평행 이동 도형들의 집합이 회전 기하 덮개 문제의 정준 변환 도형들의 집합을 포함한다는 것을 보임으로써, 볼록 다각형에 대한 회전 기하 덮개 문제를 이산화하는 알고리듬을 설계하였다. 이 알고리듬은 회전 각도에 따른 점대칭 그래프의 변화를 추적하여 모든 각도에서의 정준 평행 이동 도형들의 집합을 구성한다.
본 연구를 통해 개발한 이산화 알고리듬의 응용가능성을 확인하기 위하여 분산 센서 네트워크에서의 최소 센서 커버 문제와 복수 표적 추적을 위한 펄스 도플러 위상배열 레이더에서의 펄스 삽입 문제에 이산화 알고리듬을 활용하였다. 이 두 문제의 연속적인 해 공간은 문제의 정식화와 최적해 도출에 있어서의 난점을 유발하는 핵심적인 요인인데, 이산화 알고리듬을 통해 해 공간을 변환하여 조합 최적화 문제로 환원함으로써 이를 해결하였다. 또한 이산화된 각 문제를 효과적으로 해결하기 위한 휴리스틱 기법을 제안하고, 이를 최적해와 비교하는 수치 시뮬레이션을 수행하여 기법의 실효성을 확인하였다.
