변형된 선분 센터를 구하는 선형 알고리즘
김범준, 신찬수, 좌경룡 · 한국정보과학회 학술발표논문집 · 1999
본 논문은 두 개의 선으로 이루어진 강에 의해 분리된 평면 위의 점들의 집합 P, Q가 χ좌표에 따라 정렬되어 주어질 때, 임의의 P_i ∈ P와 q_j ∈ Q를 잇는 경로의 최대 길이를 최소화하도록 다리를 건설하는 문제를 다룬다. 본 논문에서는 L₂-거리상에서 다리의 위치를 결정하는 선형 알고리즘을 제안하고, L₁-거리와 L∞ 거리에서 점들의 집합 P와 Q가 정렬되지 않았을 때 같은 문제를 해결하는 선형 알고리즘을 제시한다. 그리고 다리를 수직으로만 건설하는 문제에 대해서도 제시한 알고리즘을 약간의 변형을 통해 적용할 수 있음을 증명하였다.
Cited by 0 works.