http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Computing a Minimum-Dilation Spanning Tree is NP-hard
Otfried Cheong(정지원),Herman Haverkort,Mira Lee(이미라) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2A
Given a set S of n points in the plane, a minimum-dilation spanning tree of S is a tree with vertex set S of smallest possible dilation. We show that given a set S of n points and a dilation δ > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most δ exists.
두 평면 볼록집합의 겹치는 영역을 최대화하는 강체운동을 구하는 근사 알고리즘
박종대(Chong-Dae Park),신찬수(Chan-Su Shin),안희갑(Hee-Kap Ahn),정지원(Otfried Cheong),AntoineVigneron(Antoine Vigneron) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1
본 논문에서는 평면 상에 두 블록집합 P와 Q와 주어졌을 때, P를 강체운동 하에서 수평이동 및 회전이동하여 Q와 겹치는 영역이 근사적으로 최대가 되는 알고리즘을 제시한다. 임의의 양의 상수 ε이 주어졌을 때, 본 알고리즘은 가장 많이 겹치는 넓이의 1-ε 배를 보장하는 P의 겅체운동을 O(1/ε)번의 기하 질의와 O(1/ε²)log(1/ε) 시간 내에 구할 수 있다. 특히 P와 Q가 블록다각형일 때, O(1/ε)logn+(1/ε²)log(1/ε) 시간에 구한다. 만약 수평이동만 사용할 경우는 O((1/ε)log+(1/ε)log(1/ε)) 시간에 구할 수 있다.
안희갑(Hee-Kap Ahn),배상원(Sang-Won Bae),정지원(Otfried Cheong) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.3·4
평면상에서 이동하는 자동차와 같은 로봇은 이동방향을 변경할 때 제한된 곡률(curvature)로 서서히 방향을 바꿀 수밖에 없다. 본 논문은 물체의 동선의 곡률이 제한되어 있을 경우, 한 구성에서 출발하여 목표점에 이르는 최단경로는 CC 혹은 CS 타입(C는 원호(circular arc), S는 선분(line segment)을 의미한다), 혹은 이들의 부분문자열 타입이 된다는 사실을 기하학적 성질만을 이용하여 증명하였다. 본 연구결과를 이용하여, 시작점 구성에서 출발하여 목표점, 혹은 목표다각형에 도달하는 최단경로는 다각형의 공간복잡도의 선형시간에 계산 가능하다. A point-wise car-like robot moving in the plane changes its direction with a constraint on turning curvature. In this paper, we consider the problem of computing a shortest path of bounded curvature between a prescribed initial configuration (position and orientation) and a polygonal goal, and propose a new geometric proof showing that the shortest path is either of type CC or CS (or their substring), where C specifies a non-degenerate circular arc and S specifies a non-degenerate straight line segment. Based on the geometric property of the shortest path, the shortest path from a configuration to a polygonal goal can be computed in linear time.