Improved Algorithm for Constructing Euclidean City Voronoi Diagrams

Sang Won Bae(배상원),Jae-Hoon Kim(김재훈),Kyung-Yong Chwa(좌경룡) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2A

This paper presents an improved algorithm for constructing the city Voronoi diagram under the Euclidean metric given a transportation network consisting of roads having a constant number of speeds and orientations. The algorithm applies the continuous Dijkstra paradigm and its efficiency follows from new geometric insights that are first observed in this paper.

보로노이 다이아그램을 위한 동적 알고리즘

허성우(Sung Woo Hur),좌경룡(Kyung Yong Chwa) 한국정보과학회 1989 정보과학회논문지 Vol.16 No.1

본 논문에서는 한정된 평면에서 n개의 점으로 구성된 Voronoi diagram 에 새로운 한 점이 입력될 경우 그 Voronoi diagram을 O(n)시간에 수정할 수 있는 알고리즘을 제시한다. 그 알고리즘은 크게 두 부분으로 구성되는데, 첫째는 새로 입력된 점이 어느 tile 내에 입력되었는지를 O(n)시간에 검색하는 부분이고, 둘째는 Voronoi diagram을 갱신하여 새로운 Voronoi diagram을 얻는 부분인데, 이의 시간복잡도는 O(m)로써, 여기서 m은 새로 입력된 점이 포함된 tile의 꼭지점의 갯수이다. This paper presents an algorithm of O(n) time complexity for finding new Voronoi diagram, when we are given Voronoi diagram on n points and a new input point. The algorithm consists of two parts. One which has time complexity of O(n) is how to find the tile in which the new input point locates. The other is how to update the Voronoi diagram. The time complexity of the latter is O(m), where m is the number of vertics of the tile which encloses the new point.

재귀 원형군(recursive circulant) 그래프의 고장지름

김상범(Sang-beom Kim),박정흠(Jung-Heum Park),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2

본 논문에서는 최근에 [PC91]에 의해 제시된 재귀 원형군(recursive circulant) 그래프 G(2^m, 4)의 노드나 에지에 고장이 발생하였을 경우의 지름과 노드간 평균 거리에 대하여 고려한다. 한 개의 노드나 에지에 고장이 발생하였을 경우 G(2^m, 4)의 지름은 늘어나지 않으며 (m≥4인 겨우), 노드간 평균 거리도 거의 늘어나지 않음으로 보인다. 또한 m≥5인 경우의 G(2^m, 4)의 고장 지름이 m 이하임을 보였는데, 이는 같은 갯수의 노드와 에지를 갖는 하이퍼큐브 Q_m의 고장 지름 m+1보다 작은 수치이다.

高分子物質의 熱分解에 關한 硏究 (第1報) 熱天秤에 依한 硏究

성좌경,Chwa-Kyung Sung 대한화학회 1963 대한화학회지 Vol.7 No.2

The weight decrease curves of 18 kinds of polymers have been measured by thermobalance at the same condition where temperature is increased $1^{\circ}C$ per minutes under nitrogen or air atmosphere. The curves are further differentiated to obtain rate curve of weight decrease. Those curve offer a method to compare relative thermal stability, effects of oxygen or modes of thermal degradation of polymers qualitatively. The curves could be classified into following four types: Polystyrene, polymethylmethacrylate and acetal polymer belong to the first type. Those polymers depolymerize mainly into corresponding monomers, weight decrease curves are steepy up to perfect vaporization of polymers and rate curves show a relatively sharp peak. (Type I) Polyvinyl chloride represents the second type. This polymer decomposes with splitting off of hydrogen chloride. The thermogravimetric curve rises rapidly at first, then level off at the moderate weight decrease and gradually rises. Polyvinyl acetate also belongs to this class. (Type II) The modification of the second type is represented by polyester. The curve at the early stage is less steep, the leveling off at the next stage is less clear and the final rising of the curve is steeper than the normal second type. Polyamide, polyurethane, and polycarbonate belong to this type. (Type II') The thermal decomposition of the third type polymers is more complex than that of others. Various irregular chain scissions including side chain splitting and depolymerization to monomers occur simultaneously. The weight of the polymer decreases gradually and the rate curve does not show sharp peaks. Polyvinyl alcohol and diene polymers belong to this type. (Type III) Generally, polycondensation polymers are more stable toward heat than addition polymers and polymers having aromatic nucleus show good thermal stability. Polymers having tertiary carbon atoms such as polystyrene or polypropylene and acetal resin start decomposition under airatmosphere at the temprature below $50^{\circ}C$ or more of the temperature where the polymers start decomposition under nitrogen atmosphere.

완전이진트리와 트리메쉬의 재귀원형군 G(2^m,4)에 대한 임베딩

박상민(Sang-Min Park),김숙연(Sook-Yean Kim),박정흠(Jung-Heum Park),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.4

주어진 병렬컴퓨터에서 이용가능한 프로세서의 갯수보다 더 많은 프로세서를 요구하는 문제들은 그래프 간의 다대일 임베딩을 적용하여 풀 수 있다. 본 논문에서는 완전이진트리를 병렬컴퓨터 구조로서 새로이 제안된 재귀원형군[2] 중 G(2^m,4)에 다대일 임베딩하는 방법을 제시하고, 그러한 임베딩을 이용하여 트리메쉬도 재귀원형군 G(2^m,4)에 다대일 임베딩한다. 완전이진트리는 분할정복이나 분기제한 탐색 등의 주요 알고리즘들의 기본 구조를 이루며 트리메쉬는 노드 갯수의 로그 또는 로그 제곱 시간만에 수행 가능한 효율적인 병렬 알고리즘들을 제공하므로, 이러한 임베딩들은 재귀원형군의 유용성을 증대시켜 준다. 우리는 임베딩에 있어서 프로세서의 이용도를 최대로 하거나, 프로세서 간 통신의 지연을 최소로 하는 전략을 취한다. 즉 부하율을 최적으로 하면서 연장율도 최적에 가까운 임베딩과 연장율을 최적으로 하면서 부하율도 최적에 가까운 임베딩을 구한다. 또한 완전이진트리의 임베딩에 있어서는 트리의 같은 레벨 노드들이 재귀원형군에 골고루 분산됨은 물론 밀집율이 최소가 되도록 한다. An embedding of arbitrarily large graphs into smaller graphs has important applications to the problems which require more processors than is available in a given parallel architecture. This paper describes methods for embedding a large complete binary tree into the small recursive circulant G(2^m,4) that was recently proposed in [2] as a versatile interconnection network. Using this embedding, we also embed a large mesh of trees into the small recursive circulant G(2^m,4). These embeddings enhance the capabilities of the recursive circulants because complete binary tree is a basic structure for many important algorithms such as divide-and-conquer and branch-and-bound search and mesh of trees enables so fast parallel computations that can be performed in logarithmic or log-squared time. We design these embeddings with the main focus on maximizing processor utilization or minimizing communication delays. So we get two embedding strategies: one with the optimal load factor and the near optimal dilation, and the other with the optimal dilation and the near optimal load factor. Furthermore, in embedding the complete binary tree we evenly distribute the same level nodes to the nodes of the recursive circulants and make the congestion the minimum.

직선상에서 최대구간을 찾는 최적 알고리즘

허성우(Sung Woo Hur),좌경룡(Kyung Yong Chwa),신성룡(Sung Yong Shin) 한국정보과학회 1988 한국정보과학회 학술발표논문집 Vol.15 No.2

본 연구에서는 x축상에 실수값의 weight가 부여된 n개의 점이 있을 때 어떤 interval을 찾아 그 interval내에 있는 점들의 weight 합이 최대가 되도록 하는, 즉 maximum interval을 찾는 최적 알고리즘을 제시한다. 또한 이 알고리즘을 이용하면 평면상에 실수값의 weight가 부여된 n개의 점이 있을 때 xy축에 평행한 어떤 직사각형을 찾아 그 직사각형내에 놓여있는 점들의 weight 합이 최대가 되도록 하는, 즉 maximum rectangle을 쉽게 찾을 수 있음을 보였다.

Recursive Circulant 그래프의 연결도

정성우(Sung-Woo Jung),김숙연(Sook-Yeon Kim),박정흠(Jung-Heum Park),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.1

본 논문에서는 최근에 제안된 다중컴퓨터 위상인 Recursive Circulant 그래프 G(N, d)의 연결도(connectivity)에 관련된 새로운 연구 결과를 기술한다. 모든 양수 N에 대해서 G(N, d)의 연결도와 에지 연결도가 G(N, d)의 분지수(degree)와 같음을 증명하고, N=cd^p, 1≤c<d, p는 정수, 일때 G(cd^p, d)는 길이가 6이상인 사이클 그래프가 아니면 super-k임과 길이가 4이상인 사이클 그래프가 아니면 super-λ임을 보인다.

절단 사각 듀얼을 갖는 평면그래프의 특성

박상민(Sang-Min Park),신찬수(Chan-Su Shin),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.1A

VLSI 회로 설계나 건축 설계에서 모듈 사이의 인접관계를 이용하여 평면 계획을 구하는 문제는 그래프의 사각 듀얼을 이용하여 해결할 수 있다. 이 때 설계하고자 하는 건문이나 회로의 규모가 커질수록 모듈 사이의 계층 구조가 요구된다. 사각 듀얼에서 계층 구조를 표현하려면 절단 구조를 갖도록 해야 한다. 본 논문에서는 주어진 그래프가 절단 구조를 갖는 사각 듀얼을 허용하는가에 대한 필요충분조건을 제시한다.

단순 다각형의 교차에 관한 알고리즘

좌경룡(Kyung-Yong Chwa),김성권(Sung-Kwon Kim),도정인(Jeong-In Do) 한국정보과학회 1983 정보과학회논문지 Vol.10 No.4

The intersection problems for simple polygons are considered. Given k polygons in the plane, j-fold region is the region which lies within at least j polygons, 1≤j≤k We present two O ((n+s)log n) algorithms for finding j-fold region and for computing the area of the j-fold region, respectively, where n is the total number of line segments of k polygons and s is the number of intersections among the n line segments. 단순 다각형들에 관한 새로운 교차 문제를 제안하였다. 평면상에 주어진 k개의 단순 다각형에 대해, 임외의 j, 1≤j≤k,에 대한 j-fold region을 적어도 j개의 단순 다각형에 속하는 모든 점들로 이루어지는 지역으로 정의한다. n이 k개의 단순 다각형의 꼭지점의 총 개수이고, s가 선분들간의 교차점의 갯수일 때, j-fold region과 그 면적을 구하는 0((n+s)logn) 알고리즘을 제시하였다.

도로망이 설치된 평면에서의 보로노이 다이어그램

배상원(Sang Won Bae),좌경룡(Kyung-Yong Chwa) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1A

본 논문에서는 유클리드 평면상에 도로망이 주어져 있어서 여행자들이 그 도로들을 이용하여 더욱 빠르게 이동할 수 있는 경우를 가정한다. 이 때, 두 점 사이의 거리는 기하학적 직선거리가 아닌 주어진 도로들을 이용하여 두 점 사이를 이동할 때 필요한 최소시간으로 측정한다. 본 논문에서는 이러한 새로운 거리 척도를 고려할 때에 보로노이 다이어그램이 어떤 특성을 갖는가를 연구하며 그것을 이용하여 보로노이 다이어그램을 효율적으로 계산하는 알고리즘을 제시한다. 이 알고리즘은 O(nm²logn+m³logm)의 시간과 O(m(n+m))의 공간을 필요로 한다. 이 때, n은 주어진 싸이트의 개수이고 m은 주어진 도로의 개수이다.