모든 색을 커버하는 최소 두께 직사각형 고리를 계산하는 알고리즘 


44권  3호, pp. 246-252, 3월  2017


PDF

  요약

이 논문에서는 모든 색을 커버하는 최소 두께를 갖는 축에 평행한 직사각형 고리를 계산하는 알고리즘을 최초로 제안한다. 직사각형 고리란 임의의 직사각형과 그 오프셋 사이의 닫힌 영역을 말하며, 따라서 두 개의 직사각형으로 정해진다. 이 때, 두 직사각형을 각각 외부 및 내부 직사각형이라 부른다. 직사각형 고리의 두께는 그것을 결정하는 외부 및 내부 직사각형 사이의 거리로 정의된다. 평면 위에 k개의 색깔을 가지는 n개의 점이 주어질 때에, 임의의 직사각형 고리가 각 색깔 별 점을 적어도 하나 이상 포함하게 되면, 그것이 모든 색을 커버한다고 말한다. 이전에는 모든 색을 커버하는 최소 두께 직사각형 고리를 계산하는 알고리즘이 알려진 바 없다. 따라서 우리는 이 문제에 대한 최초의 알고리즘을 제시한다. 시간 복잡도는 O(n-k)³nlogn)이다.


  통계
2022년 11월부터 누적 집계
동일한 세션일 때 여러 번 접속해도 한 번만 카운트됩니다. 그래프 위에 마우스를 올리면 자세한 수치를 확인하실 수 있습니다.
  논문 참조

[IEEE Style]

S. W. Bae, "An Algorithm for Computing a Minimum-Width Color-Spanning Rectangular Annulus," Journal of KIISE, JOK, vol. 44, no. 3, pp. 246-252, 2017. DOI: .


[ACM Style]

Sang Won Bae. 2017. An Algorithm for Computing a Minimum-Width Color-Spanning Rectangular Annulus. Journal of KIISE, JOK, 44, 3, (2017), 246-252. DOI: .


[KCI Style]

배상원, "모든 색을 커버하는 최소 두께 직사각형 고리를 계산하는 알고리즘," 한국정보과학회 논문지, 제44권, 제3호, 246~252쪽, 2017. DOI: .


[Endnote/Zotero/Mendeley (RIS)]  Download


[BibTeX]  Download



Search




Journal of KIISE

  • ISSN : 2383-630X(Print)
  • ISSN : 2383-6296(Electronic)
  • KCI Accredited Journal

사무국

  • Tel. +82-2-588-9240
  • Fax. +82-2-521-1352
  • E-mail. chwoo@kiise.or.kr