최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기정보과학회논문지. Journal of KISS (a):computer systems and theory. A, v.25 no.9, 1998년, pp.989 - 996
김정현 , 신찬수 , 김성권 , 좌경룡
2-중심문제는 이차원 평면상에 주어진 n개의 점들을 최소의 반지름을 가지는 크기가 같은 두 원으로 포함하는 문제를 말하는데, 최근 1997년에 Eppstein은 O(n log²n)의 시간복잡도를 가지는 알고리즘을 제시하였다. 볼록다각형에서의 2-중심문제는 이차원평면상에 주어진 볼록다각형을 최소의 반지름을 가지는 크기가 같은 두 원으로 포함하는 문제이다. 본 논문에서는 볼록다각형에서의 2-중심문제에 대해서 O(n² log^5n)의 시간복잡도를 가지는 알고리즘을 제시한다. 이 알고리즘은 Megiddo가 제시한 매개변수 탐색 기법을 사용하였는데, 이 기법을 사용하기 위해서는 우선 반지름이 r로 고정된 두 원으로 주어진 볼록다각형을 포함할 수 있는 지를 판단하는 결정문제를 해결해야 한다. 본 논문에서는 이 결정문제에 대해서 O(n² log²n) 시간에 수행되는 순차알고리즘과 O(n²) 의 프로세서(processor)를 사용하여 O(log²n)시간에 수행되는 병렬알고리즘을 각각 제시한다.
The 2-center problem for a convex polygon G is to cover G by two congruent closed disks whose radius is as small as possible. The standard 2-center problem that covers a set of n points has been studied extensively. The best algorithm to the standard 2-center problem, due to Eppstein, runs in O(n l...
※ AI-Helper는 부적절한 답변을 할 수 있습니다.