Earticle

Home 검색결과

결과 내 검색

발행연도

-

학문분야

자료유형

간행물

검색결과

검색조건
검색결과 : 8
No
1

직사각형으로 분할된 영역 비교 알고리즘

정해재

한국융합보안학회 융합보안논문지 제6권 제2호 2006.06 pp.53-60

※ 기관로그인 시 무료 이용이 가능합니다.

CAD나 화상 처리와 같은 응용에서는 다각형으로 구성된 다양한 기하 객체를 다룬다. x축과 y축에 평행한 변을 가지는 다각형은 효율적인 조작을 위해 단순 다각형인 직사각형으로 흔히 분할된다. 그러나 동일한 기하 객체 또는 영역이라 할지라도 분할 방법에 따라 직사각형의 수, 크기 및 모양에 있어 전혀 다르게 된다. 따라서 CAD 또는 화상과 같은 장면으로부터 추출된 두 개의 직사각형 집합이 동일한 영역을 나타내는지 판단하는 알고리즘이 요구된다.본 고에서는 직사각형들로 구성된 두 집합을 효율적으로 비교하는 알고리즘을 제안한다. 제안된 알고리즘은 기존의 훑기에 근거한 알고리즘에 비해 간단할 뿐만 아니라, 균형이진트리를 이용한 알고리즘에서의 중첩 직사각형 수 O(n2)을 O(nlogn)으로 줄인다.
In the applications such as CAD or image processing, a variety of geometric objects are manipulated. A polygon in which all the edges are parallel to x- or y-axis is decomposed into simple rectangles for efficient handling. But, depending on the partitioning algorithms, the same region can be decomposed into a completely different set of rectangles in the number, size and shape of rectangles. So, it is necessary an algorithm that compares two sets of rectangles extracted from two scenes such as CAD or image to see if they represent the same region.This paper proposes an efficient algorithm that compares two sets of rectangles. The proposed algorithm is not only simpler than the algorithm based on sweeping method, but also reduces the number O(n2) of overlapped from the algorithm based on a balanced binary tree to O(nlogn).

4,000원

2

묵시 다원 AM-힙

정해재

[Kisti 연계] 한국정보처리학회 정보처리학회논문지/컴퓨터 및 통신 시스템 Vol.7 No.12 2018 pp.289-294

협약을 통해 무료로 제공되는 자료로, 원문이용 방식은 연계기관의 정책을 따르고 있습니다.

본 논문에서는 AM-힙의 다원 버전인 AM(d)-힙이라고 하는 묵시 다원 우선순위 큐를 제안하며, 제안된 AM(d)-힙에서는 삽입에 O(1) 전이시간이 걸리고 삭제 연산에 O(logn) 시간이 걸린다. 실험 결과에 따르면, 전체적으로 d가 4 또는 8일 때 가장 우수한 성능을 나타내었다. 기존의 후위힙과 비교하면 AM(d)-힙이 약 1.5~1.8배 빠른 것으로 나타났다.
This paper proposes an implicit d-ary priority queue, called AM(d)-heap that is a generalized version of AM-heap, in which insert operation takes constant amortized time and remove operation takes O(logn) time. According to our experimental results, the best performance was shown when d is 4 or 8. Also, AM(d)-heap is about 1.5~1.8 times faster than the postorder heap.

원문보기
3

우선순위 큐 성능 시험에 관한 연구

정해재

[Kisti 연계] 한국정보처리학회 정보처리학회논문지 A Vol.a17 No.4 2010 pp.167-172

협약을 통해 무료로 제공되는 자료로, 원문이용 방식은 연계기관의 정책을 따르고 있습니다.

본 논문에서는 우선순위 큐에 대한 성능 시험 모델을 제안하고, 제안된 모델에 따라 대표적인 우선순위 큐인 전통 힙, 후순위 힙, 및 페어링 힙의 성능 시험 결과를 보여준다. 이들 중 전통 힙이 분석된 시간복잡도에 있어서 최악인 것으로 알려져 있다. 그러나 제안된 성능 시험 모델에 근거한 성능 시험 결과에 따르면, 포인터를 사용하는 페어링 힙이 가장 느리고 전통 힙이 가장 빠른 것으로 나타났다. 두 묵시 힙에 대해서도, 분석된 시간복잡도로는 후순위 힙이 전통 힙보다 우수하지만, 성능 시험 결과는 반대인 것으로 나타났다.
This paper proposes a set of runtime test models for priority queues and shows the runtime test results based on the proposed test models for the representative priority queues: the traditional heap, post-order heap, and pairing heap. Among these heaps, the traditional heap is the worst in time complexity analyzed. But, according to our experimental results based on the test models proposed, it is shown that the slowest one is the pairing heap that utilizes pointers and the fastest one is the traditional heap. For the two implicit heaps, these results are in contrary to the fact that the post-order heap is better than the traditional heap in time complexity analyzed.

원문보기
4

상수 삽입 전이 시간을 가지는 양단 우선순위 큐

정해재

[Kisti 연계] 한국정보처리학회 정보처리학회논문지 A Vol.a16 No.3 2009 pp.217-222

협약을 통해 무료로 제공되는 자료로, 원문이용 방식은 연계기관의 정책을 따르고 있습니다.

우선순위 큐는 스케줄링, 정렬, 유전자 검색과 같은 우선순위에 따른 검색, 최단거리 계산과 같은 응용에 사용될 수 있다. 본 논문에서 제안하는 배열을 이용한 양단 우선순위 큐 자료구조는 삽입과 삭제 연산에 각각 O(1) 전이시간과 O(logn) 시간이 걸린다. 본 저자가 알고 있는 한, 지금까지의 배열을 이용한 양단우선순위 큐 알고리즘은 삽입과 삭제에 모두 O(logn) 시간이 걸린다.
Priority queues can be used in applications such as scheduling, sorting, retrival based on a priority like gene searching, shortest paths computation. This paper proposes a data structure using array representation for double-ended priority queue in which insertion and deletion takes O(1) amortized time and O(logn) time, respectively. To the author's knowledge, all the published array-based data structures for double ended priority queue support O(logn) time insertion and deletion operations.

원문보기
5

배열 표현을 이용한 M-힙에서 삽입/삭제 알고리즘

정해재

[Kisti 연계] 한국정보처리학회 정보처리학회논문지 A Vol.a13 No.3 2006 pp.261-266

협약을 통해 무료로 제공되는 자료로, 원문이용 방식은 연계기관의 정책을 따르고 있습니다.

스케줄링, 정렬, 및 최단 거리 계산 네트워크 문제 등과 같은 응용에 이용될 수 있는 우선 순위 큐 중, 피보나치 힙, 페어링 힙, 및 M-힙은 포인터를 이용하는 자료 구조이다. 본 논문에서는 [1]에서 문제점으로 남겨두었던 M-힙을 배열을 이용하여 표현한 MA-힙(M-heap with an array representation)를 제안한다. MA-힙은 M-힙과 동일한 시간 복잡도인 O(1) 삽입 전이 시간과 O(logn) 삭제 시간 복잡도를 가지며, 단순한 전통적인 힙에 근거하고 있기 때문에 [5]에서 제안된 힙보다 구현이 매우 용이하다.
Priority queues can be used in applications such as scheduling, sorting, and shortest path network problem. Fibonacci heap, pairing heap, and M-heap are priority queues based on pointers. This paper proposes a modified M-heap with an way representation, called MA-heap, that resolves the problem mentioned in [1]. The MA-heap takes O(1) amortized time and O(logn) time to insert an element and delete the max/min element, respectively. These time complexities are the same as those of the M-heap. In addition, it is much easier to implement an MA-heap than a heap proposed in [5] since it is based on the simple traditional heap.

원문보기
6

8-?*: 빠른 8-원 묵시 우선순위 큐

정해재

[Kisti 연계] 한국정보처리학회 정보처리학회논문지 A Vol.a11 No.3 2004 pp.213-216

협약을 통해 무료로 제공되는 자료로, 원문이용 방식은 연계기관의 정책을 따르고 있습니다.

스케줄링이나 정렬과 같은 응용에 이용될 수 있는 우선순위 큐는 포인터를 사용하는 것과 이용하지 않고 묵시적으로 표현하는 두 가지가 있다. 묵시 우선순위 큐는 메모리 이용에 있어서 포인터를 사용하는 것보다 효율적이다. 묵시 우선순위 에는 이진 트리에 근거한 전통적인 2-힙이 있는데, 이는 캐쉬 메모리를 효율적으로 이용하는 8-원 트리에 근거한 8-힙보다 느린 것으로 나타났다. 본 논문에서는 구현하기 쉽고 빠른 새로운 묵시 우선순위 큐인 8-힙*를 제안한다. 실험을 통하여 8-힙*가 2-힙 뿐만 아니라 8-힙보다 빠름을 보인다.
Proirity queues(PQ) can be used in applications such as scheduling or sorting. The data structures for PQ can be constructed with or without pointers. The implicit representation without pointers uses less memory space than pointer-based representation. It if shown that a 2-heap, a traditional Implicit PQ based on a binary tree, is slower than an f-heap based on a 8-ary tree. This is because 8-heap utilizes cache memory more efficiently This paper presents a novel fast implicit heap called 8-heap* which is easier to implement. Experimental results show that the 8-heap* is faster than 8-heap as well as 2-heap

원문보기
7

4-딥✽ : 캐쉬를 이용한 빠른 4-원 딥

정해재

[Kisti 연계] 한국정보처리학회 정보처리학회논문지 A Vol.a11 No.7 2004 pp.577-582

협약을 통해 무료로 제공되는 자료로, 원문이용 방식은 연계기관의 정책을 따르고 있습니다.

스케쥴링이나 정렬과 같은 응용에 이용될 수 있는 양단 우선순위 큐는 포인터를 사용하는 것과 포인터를 이용하지 않고 묵시적으로 표현하는 두 가지가 있다. 묵시 자료 구조는 메모리 이용에 있어서 포인터를 사용하는 것보다 효율적이다. 본 논문에서는 캐쉬 메모리를 효율적으로 이용하는 새로운 묵시 양단 우선순위 큐인 4-딥$\ast$를 제안한다. 실험을 통하여, 제안된 4-딥$\ast$가 이진 트리에 근거한 딥뿐만 아니라 대칭 최소-최대 합보다 빠름을 보인다.
Double-ended Proirity queues(DEPQ) can be used in applications such as scheduling or sorting. The data structures for DEPQ can be con-structed with or without pointers. The implicit representation without pointers uses less memory space than pointer-based representation. This paper presents a novel fast implicit heap called 4-deapr$\ast$ which utilizes cache memory efficiently. Experimental results show that the 4-deap$\ast$ is faster than symmetric min-max heap as well as deap.

원문보기
8

k 사다리꼴 셋의 영역 중심 비교 알고리즘

정해재

[Kisti 연계] 한국정보처리학회 정보처리학회논문지 A Vol.a10 No.6 2003 pp.665-670

협약을 통해 무료로 제공되는 자료로, 원문이용 방식은 연계기관의 정책을 따르고 있습니다.

반도체 생산을 위한 마스크 자동 생성과 같은 기하 객체를 다루는 응용에서는, 사다리꼴로 분할된 수 많은 다각형으로 구성된 도면에 새로운 다각형을 추가하거나 삭제하기 위해 사다리꼴 삽입, 삭제, 및 검색 연산을 한다. 동일한 다각형에 대해 분할된 사다리꼴은 사용된 분할 알고리즘에 따라 모양, 크기 등에 있어서 다르게 된다. 사다리꼴로 구성된 기하 객체를 다루는 프로그램을 검증하는 것과 같은 예에서는 구성된 도면의 관심 부분을 나타내는 여러 사다리꼴 셋을 비교하는 알고리즘이 필요하다 본 논문에서는 k개 도면의 관심 영역으로부터 각각 추출된 사다리꼴로 구성된 k 셋이 주어졌을 때, 그 k 셋이 형성하는 기하 도형틀이 동일한지 아닌지를 비교하는 새로운 알고리즘을 제시한다. 제시된 알고리즘은 각 셋이 공히 n개의 사다리꼴을 포함하고 있다고 가정할 때, O(2$^{k-2}$ $n^2$(log n+k))시간 복잡도를 가진다. 제시된 알고리즘은 입력셋의 수 k(<<n)가 적을 때 훑기 중심 알고리즘과 동일한 시간 복잡도 O( $n^2$ log n)를 가지며, 특히 k 셋이 동일하거나 대부분 동일한 사다리꼴들로 구성되어 있을 경우 훑기 중심 알고리즘보다 kn배까지 빠른 것은 나타났다.다.
In the applications like automatic masks generation for semiconductor production, a drawing consists of lots of polygons that are partitioned into trapezoids. The addition/deletion of a polygon to/from the drawing is performed through geometric operations such as insertion, deletion, and search of trapezoids. Depending on partitioning algorithm being used, a polygon can be partitioned differently in terms of shape, size, and so on. So, It's necessary to invent some comparison algorithm of sets of trapezoids in which each set represents interested parts of a drawing. This comparison algorithm, for example, may be used to verify a software program handling geometric objects consisted of trapezoids. In this paper, given k sets of trapezoids in which each set forms the regions of interest of each drawing, we present how to compare the k sets to see if all k sets represent the same geometric scene. When each input set has the same number n of trapezoids, the algorithm proposed has O(2$^{k-2}$ $n^2$(log n+k)) time complexity. It is also shown that the algorithm suggested has the same time complexity O( $n^2$ log n) as the sweeping-based algorithm when the number k(<< n) of input sets is small. Furthermore, the proposed algorithm can be kn times faster than the sweeping-based algorithm when all the trapezoids in the k input sets are almost the same.

원문보기
 
페이지 저장