채널에서 특정 위치들을 선으로 연결하는 채널 라우팅(channel routing) 문제는 집적 회로의 여러 레이아웃 문제에서 발생한다. 특정 위치들을 어디에 놓을 것이지 또는 어떻게 연결할 위치들을 선택할 지와 같은 결정은 라우팅 이전에 이루어져야 한다. 본 논문에서는 두 개의 수평선 상에 위치들이 놓여 있을 때, 이 위치들을 연결하는 문제를 다룰 것이다.

평면상에 일정한 간격을 두고 두 개의 수평선 U와 L이 주어지는데 U는 L보다 위쪽에 위치한다. 위쪽 수평선 U에는 시작점이라 불리는 n개의 점들이 존재하고 아래쪽 수평선 L에는 끝점이라 불리는 m개의 점들이 존재한다. 그리고 항상 n ≤ m을 만족한다. 또한 위쪽 수평선 U상의 점들은 p가지의 색으로 구별된다.

색을 k∈{ 1, 2, … , p}인 정수로 나타낼 때, U상의 점 는 색이 k인 i번째 점을 나타내고 L상의 점은 b_j 로 나타낸다. 1 ≤ , b_j ≤ m 이고 색 k인 점 의 총 수를 n_k로 나타낸다. 우리는 U상의 점들의 집합 P_U에서 L상의 점들의 집합 P_U로의 일대일 함수 f : P_U→P_L를 찾고자 한다. 점 가 점 b_j = f ( )로 대응되었다는 것은 점 에서 점 b_j로 선분이 그어졌음을 의미한다. 여기서 함수 f에 의해서 생긴 선분들에 대해서 색 k인 시작점을 연결하는 선분을 k-색 선분 (k-color segment)이라고 부른다. 그러면 k-색 밀도(k -color density)란 수직선을 왼쪽에서 오른쪽으로 이동하면서 만나는 k-색 선분들의 개수를 세었을 때, 만나는 k-색 선분들의 개수가 최대가 됐을 때 그 때의 선분 개수를 말한다. 다시 말해서, k-색 밀도란 모든 실수 x 에 대해서 ≤ x < b_j 또는 > x ≥ b_j를 만족하는 k-색 선분들의 개수의 최대값으로 정의한다. 결과적으로 우리는 선분들에 대한 밀도(density)를 k-색 밀도들의 최대값으로 정의할 수 있다. 문제는 이 밀도가 최소가 되도록하는 일대일 함수 f 를 찾는 것이다.

본 논문에서는 최소 밀도를 주는 일대일 함수 f를 찾기 이전에 임의의 상수 d가 주어질 때, 밀도가 d이하인 일대일 함수 f가 존재하는지 여부를 묻는 결정 문제를해결할 것이다. 이 결정 문제 알고리즘을 이용해서 최소 밀도 값 d^*를 계산하고 이 밀도 값을 주는 일대일 함수 f를 찾을 것이다.

본 논문과 가장 밀접한 관련이 있는 논문들은 [1, 2]이다. [1]에서는 수평선 U상의 점들이 모두 같은 색을 가지는 경우를 다룬다. 3장에서 다룰 결정문제에 대해서 저자들은 O(n + m)시간 알고리즘을 제안하였다. 최소 밀도를 찾는 최적화 문제에 대해서도 또한 O(n + m)시간 알고리즘을 제안하였다.

[2]에서는 수평선 U상의 점들이 단지 두 가지 종류의 색을 갖는 문제를 연구하였다. 저자들은 이 경우에 대한 결정문제에 대해서 O((n + m)log(n + m))시간 알고리즘을 제안하였다. 또한 최소 밀도 값을 O(n + m)시간에 찾을 수 있음을 보였고 이 최소 밀도 값을 주는 일대일 함수 f를 O((n + m)log(n + m))시간에 찾을 수 있음을 보였다. 본 논문은 이 논문의 모델을 확장해서 U상의 점들이 p가지의 서로 다른 색을 가지는 경우로 일반화할 것이다.

우리는 채널 라우팅 문제를 연구한 여러 다양한 논문들을 찾을 수 있다. [3]에서는 점들을 연결하는 선분들 이 수직과 수평 선분 부분들로 이루진 경우를 다룬다. 이 때 수평 선분 부분들의 수를 최소로 하는 레이아웃을 찾는 것이 목적이다.

[4]에서는 L상의 점들을 순서는 유지하면서 오른쪽으로 이동시키는 회전(rotation) 연산을 생각한다. 이 때 최소 밀도 값을 주는 회전 연산을 찾는 문제를 연구하였다.

[5]에서는 U 또는 L상의 점들이 요소(component) 안에 놓여 있는 경우를 다룬다. 그리고 이 요소들은 일직선상에서 왼쪽 또는 오른쪽으로 이동 가능하다. 이 요소들을 이동시켜 밀도 값이 최소가 되도록 하는 문제를 연구하였다.

이 장에서는 다음과 같은 결정문제 P1을 다룰 것이다:

P1 : 임의의 정수 d가 주어질 때, 밀도가 d보다 작거나 같은 선분들을 생성하는 일대일 함수 f가 존재하는가?

순서쌍 u = (i₁, i₂, … , i_p )에 대해서, 부분할당 f_u,e을 정의한다. 이것은 각각의 색 k = 1, …, p에 대해서, 점 , …. 가 벌써 L상의 점과 연결되었고, 점 b_e 이 연결된 L상의 가장 오른쪽 점이란 것을 의미한다.이 때, 다음을 만족하는 부분할당 f_u,e을 d-할당이라고 부른다: 각각의 색 k에 대해서, f_u,e은 색 k인 시작점들이 k-색 밀도가 ≤ d를 만족하는 할당으로 확장될 수 있다.

d-할당 f_u,e, e ≤ h, 이 주어질 때, 끝점 b_{h + 1}의 k-레이블 j_k를 정의한다. 각 k에 대해서, f_u,e에 b_{h + 1}과 을 연결하는 선분을 추가할 때 밀도가 d + 1이되면 j_k = 0. j_k ≠ 0이면, j_k = 1 또는 j_k = 2. d-할당 f_u,e가 그것의 k-색 밀도가 ≤d를 만족하는 할당으로 확장하기 위해서 b_{h + 1}가 반드시 와 연결되어야 하면, j_k = 1 . 그렇지 않다면, j_k = 2 .

아래의 표 1에서 결정 알고리즘이 주어진다. 이 알고리즘에서 함수 label은 끝점 b_{h + 1}의 모든 k-레이블들의 순서쌍 w = (j₁, … , j_p)를 출력한다. 여기서 함수 label의 구현을 구체적으로 설명할 것이다. 각 색 k 에 대해서, j_k = 0, 다시 말해서, b_{h + 1}과 을 연결하면 k-색 밀도가 d + 1가 되는지 결정하는 것은 O(1)시간에 할 수 있다. j_k = 1 또는 j_k = 2 인지 결정하기 위해서 우리는 [2]에서와 같은 균형 이진트리 T_k를 사용할 것이다.

점 , … , 와 b_f(1), …, b_f(ik), b_{h + 1}, …, b_m을 정렬한 후, 각 점들을 T_k의 잎노드에 왼쪽에서 오른쪽으로 저장한다. T_k의 내부노드 u 는 부가적인 정보들을 저장해서 자신이 루트가 되는 서브트리의 잎노드들에 대한 k-밀도를 계산할 수 있도록 한다. 그러면 이 트리 T_k에서 b_{h + 1}을 제거하는 질의를 수행한다. 결과로 k-밀도가 d + 1로 증가하면 j_k = 1이고 아니면 j_k = 2. 이 질의는 O(log(n_k + m))시간에 수행된다. 따라서 label 함수의 출력을 얻기위해서 모든 k에 대해서 이 것을 수행하면 O(plog(n + m))시간이 소요된다. 마지막으로 결정 알고리즘이 끝점 b_{h + 1}을 어떤 색 c인 시작점과 연결하기로 결정한다면 k ≠ c인 모든 색 k에 대해서 트리T_k에서 b_{h + 1}을 제거해서 트리를 업데이트 한다.

결정 알고리즘은 색 k인 시작점들과 끝점들을 각각 왼쪽에서 오른쪽으로 고려하면서 수행한다. label 의 결과 순서쌍 w = (j₁, … , j_p)에서 하나 이하의 j_k가 1이면, 현재 고려되는 끝점 b_{h + 1}과 색 k인 시작점 을 연결하는 선분 (a_ik + 1, b_{h + 1})을 추가한다. 그렇지 않으면, 다시 말해서, 모두가 1이 아니면, j_k = 2인 색 k중에 가장 작은 k의 시작점과 끝점을 연결한다. 알고리즘 진행 중에 w안에 적어도 두 개 이상의 j_k가 1이 되면, 일대일 함수 f는 존재하지 않는다. 결과적으로 위 결정 알고리즘은 O(p(n + m)log(n + m))시간에 수행됨을 알 수 있다.

이 장에서는 다음과 같은 최적화문제 P2를 다룰 것이다:

P2 : 일대일 함수 f에 의해 생성되는 선분들의 최소밀도를 찾으시오.

이 문제는 3장의 결정 알고리즘을 이용해서 풀 것이다. 다시 말해서, 결정 알고리즘을 이용해서 밀도 값 d에 대해서 이분검색(binary search)을 수행할 것이다.

1 ≤ x, y ≤ M 인 모든 x , y에 대해서, up_k(x, y) 는 위치가 ≥ x이고 ≤ y인 색 k인 시작점들의 수로 정의하고, down (x, y)는 위치가 ≥ x이고 ≤ y인 끝점들의 수로 정의한다. 또한 out_k (x, y)는 up_k(x, y) - down (x, y) 로 정의한다. 이 정의로부터 𝜓₁ (x, y) max{ out₁ (x, y), …, out_p (x, y)}, 라고 하자. 그러면 Φ₁을 다음과 같이 정의한다:

Φ₁ 가 최적 밀도 d^* 의 하한이 된다는 것, 다시 말해서, d^* ≥ Φ₁ 을 만족함을 보이기는 어렵지 않다.

보조정리 4.1. d^* ≥ Φ₁.

또한 d^*의 상한을 얻기 위해서 다음과 같이 Φ₂를 정의한다:

다음에서 우리는 Φ₂가 d^*의 상한임을 보인다.

보조정리 4.2. d^* ≤ Φ₂.

증명. 밀도 Φ₂인 일대일 함수 f가 존재함을 보임으로 충분하다. 다시 말해서, 이전 장의 결정문제 P1에 대해서 d = Φ₂일 때, 결정 알고리즘의 답이 항상 참임을 보이면 된다.

결론이 아니라고 가정하면, 다시 말해서, 결정 알고리즘이 거짓을 출력하였다고 가정하자. 알고리즘의 동작에서 점 , … , , b_{h + 1} 을 고려할 때 실패하였다면 b_{h + 1} 의 레이블 w안에는 적어도 둘 이상이 1이다. 하지만 이런 일은 일어나지 않음을 증명할 것이다.

레이블 w안에서 1의 값을 갖는 임의의 두 개의 인덱스를 j_α와 j_β라고 하자. 다시 말해서, 색 α와 β각각에 대해서, 밀도 d = Φ₂를 얻기 위해서는 b_{h + 1} 가 각각 a_{iα + 1} 과 a_{iβ + 1} 에 연결되어야만 한다.

j_α = 1 또는 j_β = 1 이 되는 다음과 같은 두 가지 이유가 있다:

먼저 j_α = 1, j_β = 1의 적어도 한 경우가 1) 때문인 경우를 생각하자. 남아있는 색 α와 β인 점들의 총 수가 남아있는 끝점들의 수를 넘어가는 순간을 생각한다. 이것이 점, , b_{t + 1}를 고려할 때 처음으로 나타난다고 가정하자. 그러면, n_α - r + n_β - s은 m - t + 1과 같다. b_{t + 1 - λ} 를 ≤ b_{t + 1} 위치에 있는 연결되지 않은 가장 오른쪽 끝점이라고 하자. 그러면 이 점에서의 레이블 w = 0. 따라서 b_{t + 1 - λ} < 이고 b_{t + 1 - λ} < . 또한 ≤ b_{t + 1 - λ} 에 위치한 끝 점들에 연결된 > b_{t + 1 - λ}과 b_{t + 1} 사이에 있는 끝점들과 연결된 시작점들의 수라고 하자. 그러면,

이것은 모순이다. 따라서 j_α = 1, j_β = 1의 어떤 경우도 1) 때문은 아니다.

남은 것은 j_α = 1, j_β = 1가 모두 2) 때문인 경우 이다. S_α를 색 α인 점들만을 고려해서 a₁, …, a_iα은 f와 같이 연결하고 남은 점들을 b_{h + 1}, …, b_m 에 연결하는 밀도 Φ₂의 해답이라고 하자. 그러면 S_α에서 적어도 하나의 좌표 x_α ≥ b_{h + 1}에 대해서 ≤ x_α에 위치한 시작점과 > x_α인 끝점을 연결하는 Φ₂개의 선분들이 존재한다. 따라서 위 조건을 만족하는 가장 왼쪽의 좌표를 x_α이라고 하자. 그러면 S_α에서 ≥ b_{h + 1}이고 ≤ x_α인 위치의 끝점들은 모두 α색의 시작점들과 연결된다. 비슷하게 색 β에 대한 S_β를 생각할 수 있고 x_β를 정의한다. 일반성의 손실 없이, x_α ≤ x_β.

위치가 > b_{h + 1}이고 ≤ x_α끝점들의 개수를 δ₁이라 하고 > b_{h + 1}이고 ≤ x_β인 끝점들의 개수를 δ₂라고 하자. 그러면 는 위치 ≤ x_α인 가장 오른쪽 색 α점이고 는 위치 ≤ x_β인 가장 오른쪽 색 β점이다. δ₃를 x_α + 1과 x_β사이의 색 α점들의 수라고 하면, 는 위치 ≤ x_β인 가장 오른쪽 색 α점이다.

우선 b_{h + 1} 왼쪽의 모든 끝점들이 연결되어 있다고 가정하자. 그러면,

이것은 모순이다.

b_{h + 1}왼쪽의 모든 끝점들이 연결되어 있지는 않다고 가정하자. b_z를 그러한 연결되지 않은 가장 오른쪽 끝점이라고 하면, < b_z인 끝점들과 연결된 각각 Φ₂개의 색 α와 β인 시작점들이 > b_z에 존재한다. 위와 비슷한 이유에 의해서 다음을 만족한다:

그러나 이것은 모순이다. 위의 두 보조정리로부터 Φ₁ ≤ d^* ≤ Φ₂임을 알 수 있다. 따라서 밀도 값 d에 대한 이분검색을 수행할 때, 위의 범위에서 수행하면 O(p(n + m)log(n + m)log(Φ₂ - Φ₁))시간에 풀수 있다.

본 논문에서는 [1, 2]에서 다루었던 문제에서 수평선 U상의 점들이 p가지의 색을 가지는 경우로 확장하였다. 임의의 상수 d가 주어질 때, 밀도가 d이하인 일대일 함수 f가 존재하는지 여부를 묻는 결정문제에 대해서 O(p(n + m)log(n + m))시간 알고리즘을 제안하였다. 또한 최소 밀도 값을 d^*를 계산하고 이 밀도 값을 주는 일대일 함수 f를 찾는 O(p(n + m)log(n + m)log(Φ₂ - Φ₁))시간 알고리즘을 제안하였다. 앞으로 채널 라우팅 문제에 대한 여러 변형 문제들에 대해서도 연구할 수 있을 것이다.