정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)
Current Result Document :
| 한글제목(Korean Title) |
히스토그램을 직사각형들로 분할하는 알고리즘 |
| 영문제목(English Title) |
Rectangular Partitioning Algorithm for Histograms |
| 저자(Author) |
김휘
안희갑
Hwi Kim
Hee-Kap Ahn
|
| 원문수록처(Citation) |
VOL 28 NO. 02 PP. 0128 ~ 0133 (2022. 02) |
한글내용
(Korean Abstract) |
히스토그램의 직사각형 분할이란 히스토그램 내부에 선분들을 그어 나뉜 직사각형들의 집합을 의미한다. 이때 각 선분은 히스토그램의 오목 꼭짓점에 인접한 것들로 제한된다. 이 논문은 히스토그램의 직사각형 분할 가운데 나뉜 직사각형들 중 가장 짧은 변의 길이가 최대인 것을 계산하는 알고리즘을 제시한다. 이 알고리즘은 히스토그램의 특수한 경우인 케이크와 계단의 두꺼운 분할을 계산하는 알고리즘을 서브루틴으로 사용하며, 분할을 구성하는 선분들이 특정 조건을 만족하도록 하는 히스토그램의 두꺼운 분할이 항상 존재한다는 관찰을 통해 탐색 공간의 크기를 줄임으로써 선형 시간과 공간을 달성한다. 이 알고리즘의 응용 분야로는 이미지 처리와 VLSI 디자인 등이 있다. |
영문내용
(English Abstract) |
We investigate the problem of partitioning a histogram H with n vertices into rectangles using disjoint line segments drawn inside H. We develop a dynamic programming algorithm that computes a thick partition of H, which maximizes the minimum side length over all resulting rectangles. As subroutines, it uses algorithms that compute a thick partition of cakes and staircases, two special kinds of histograms. We observe that there always exists a thick partition of H such that the line segments constituting the partition satisfy certain conditions. Based on this observation, the algorithm computes a thick partition in O(n) time and space. The algorithm can be useful in processing digital images and designing very-large-scale integration (VLSI) layouts. |
| 키워드(Keyword) |
히스토그램
직사각형 분할
VLSI 레이아웃 디자인
최소 변 길이
histogram
rectangular partition
VLSI layout design
minimum side length
|
| 파일첨부 |
PDF 다운로드
|
