단순 직교 다각형에서 직교 거리 문제에 관한 선형 시간 알고리즘

유관희, 좌경룡, 신성용 · 정보과학회논문지(A) · 1996

단순 직교 다각형 P에 포함되는 두 점사이의 직교 거리는 두 점을 연결하는 P 내부에 존재하는 최단 직교 경로의 길이이다. 직교 거리와 관련하여 다음과 같은 문제를 고려할 수 있다. 첫째 P 에 포함되는 임의의 두 점사이의 최장 직교 거리를 구하는 직교 지름 문제, 두번째로 P 내부의 한점 p 에서 P 내부의 임의의 다른 점까지의 최장 직교 거리가 최소인 점들의 집합을 구하는 직교 중심 문제, 마지막으로 P 내부의 한 점 p 에 대해 FVR(p)를 p 로 부터의 직교 거리가 P 의 임의의 다른 점으로 부터의 직교 거리 보다 더 길게 되는 점들의 집합이라 할 때, P 를 FVR(p)들로 분할하는 직교 최장 보로노이 (Voronoi) 다이아그램 문제이다. 본 논문에서는 단순 직교 다각형에 대해 위 세 문제를 구하는 선형 시간 알고리즘을 제시한다.

Cited by 0 works.

Authors