Discretization of geometric cover problem and its application

Abstract

본 논문은 평면 도형의 평행 이동과 회전을 포함하는 기하 덮개 문제의 이산화에 대해 다룬다. 또한 센서 배치 문제와 레이더 자원 관리에서의 펄스 스케줄링 문제에 이산화 기법을 응용한 결과를 포함하고 있다.

평면상에 주어진 $n$개의 점의 집합 $P$와 평면 도형 $T_0$에 대하여, $T_0$의 평면 변환 도형들로 이루어진 집합이 $P$의 점을 모두 포함할 때, 그러한 집합 중에서 최소의 집합을 찾는 문제를 ‘일반화된 기하 덮개 문제’로 정의한다. 본 논문에서는 평면 변환의 종류에 따라 일반화된 기하 덮개 문제를 한정시켜서, 평면 도형의 평행 이동만을 고려한 ‘기하 덮개 문제’와 평행 이동과 평면상의 회전을 포함하는 ‘회전 기하 덮개 문제’를 고려하였다. 먼저, 이 기하 덮개 문제들의 무한하고 연속적인 해 공간은 축소된 유한 해 공간으로 이산화될 수 있으며, 축소된 유한 해 공간은 서로 다른 정준 변환 도형으로 구성되어 있다는 것을 증명하였다. 이에 따라 기하 덮개 문제들은 미리 주어진 유한한 개수의 도형들로 해 공간이 구성되어 있는 기하 집합 덮개 문제로 환원시켜 해결할 수 있음을 보였다.

또한 두 기하 덮개 문제들의 이산화를 수행하는 알고리듬들을 개발하고 그 점근적 수행시간을 분석하였다. 평행 이동만을 고려한 기하 덮개 문제에서 서로 다른 정준 변환 도형들을 효율적으로 찾기 위해 ‘점대칭 그래프’라는 평면 구조를 고안하였으며, 원반, 볼록/오목 다각형 또는 유한한 수의 Jordan 곡선으로 구성된 다양한 유형의 평면 도형들에 대하여 기하 덮개 문제를 이산화하는 알고리듬들을 제시하였다. 한편, 주어진 평면 도형 $T_0$를 회전시키는 모든 각도에서의 기하 덮개 문제의 정준 평행 이동 도형들의 집합이 회전 기하 덮개 문제의 정준 변환 도형들의 집합을 포함한다는 것을 보임으로써, 볼록 다각형에 대한 회전 기하 덮개 문제를 이산화하는 알고리듬을 설계하였다. 이 알고리듬은 회전 각도에 따른 점대칭 그래프의 변화를 추적하여 모든 각도에서의 정준 평행 이동 도형들의 집합을 구성한다.

본 연구를 통해 개발한 이산화 알고리듬의 응용가능성을 확인하기 위하여 분산 센서 네트워크에서의 최소 센서 커버 문제와 복수 표적 추적을 위한 펄스 도플러 위상배열 레이더에서의 펄스 삽입 문제에 이산화 알고리듬을 활용하였다. 이 두 문제의 연속적인 해 공간은 문제의 정식화와 최적해 도출에 있어서의 난점을 유발하는 핵심적인 요인인데, 이산화 알고리듬을 통해 해 공간을 변환하여 조합 최적화 문제로 환원함으로써 이를 해결하였다. 또한 이산화된 각 문제를 효과적으로 해결하기 위한 휴리스틱 기법을 제안하고, 이를 최적해와 비교하는 수치 시뮬레이션을 수행하여 기법의 실효성을 확인하였다.