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),이현섭(Hyunseob Lee),좌경룡(Kyung-Yong Chwa),Otfried Cheong(Otfried Cheong) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.2Ⅰ
n개의 점과 이를 포함하는 직사각형 B가 주어졌을 때 B 내에서 어떤 점도 포함하지 않는 가장 큰 직사각형을 찾는 선형 근사 알고리즘을 제시한다. 찾게 되는 직사각형은 좁고 긴 모양의 것은 피하며 직사각형 B의 변에 평행해야 할 필요는 없다. 모든 방향을 고려하여 가장 큰 직사각형을 근사율 (1+ε)로 O(n+(area(B)/(αl)²) log²(α/ε)) 시간 내에 구한다.
Maximizing the overlap of two planar convex sets under rigid motions
Ahn, Hee-Kap,Cheong, Otfried,Park, Chong-Dae,Shin, Chan-Su,Vigneron, Antoine Elsevier 2007 Computational geometry Vol.37 No.1
<P><B>Abstract</B></P><P>Given two compact convex sets <I>P</I> and <I>Q</I> in the plane, we compute an image of <I>P</I> under a rigid motion that approximately maximizes the overlap with <I>Q</I>. More precisely, for any &z.epsiv;>0, we compute a rigid motion such that the area of overlap is at least 1−&z.epsiv; times the maximum possible overlap. Our algorithm uses O(1/&z.epsiv;) extreme point and line intersection queries on <I>P</I> and <I>Q</I>, plus O((1/<SUP>&z.epsiv;2</SUP>)log(1/&z.epsiv;)) running time. If only translations are allowed, the extra running time reduces to O((1/&z.epsiv;)log(1/&z.epsiv;)). If <I>P</I> and <I>Q</I> are convex polygons with <I>n</I> vertices in total that are given in an array or balanced tree, the total running time is O((1/&z.epsiv;)logn+(1/<SUP>&z.epsiv;2</SUP>)log(1/&z.epsiv;)) for rigid motions and O((1/&z.epsiv;)logn+(1/&z.epsiv;)log(1/&z.epsiv;)) for translations.</P>
The minimum convex container of two convex polytopes under translations
Ahn, Hee-Kap,Abardia, Judit,Bae, Sang Won,Cheong, Otfried,Dann, Susanna,Park, Dongwoo,Shin, Chan-Su Elsevier 2019 Computational geometry Vol.77 No.-
<P><B>Abstract</B></P> <P>Given two convex <I>d</I>-polytopes <I>P</I> and <I>Q</I> in <SUP> R d </SUP> for d ⩾ 3 , we study the problem of bundling <I>P</I> and <I>Q</I> in a smallest convex container. More precisely, our problem asks to find a minimum convex set containing <I>P</I> and a translate of <I>Q</I> that do not properly overlap each other. We present the first exact algorithm for the problem for any fixed dimension d ⩾ 3 . The running time is O ( <SUP> n ( d − 1 ) ⌊ d + 1 2 ⌋ </SUP> ) , where <I>n</I> denotes the number of vertices of <I>P</I> and <I>Q</I>. In particular, in dimension d = 3 , our algorithm runs in O ( <SUP> n 4 </SUP> ) time. We also give an example of polytopes <I>P</I> and <I>Q</I> such that in the smallest container the translates of <I>P</I> and <I>Q</I> do not touch.</P>
안희갑(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.
A New Geometric Proof on Shortest Paths of Bounded Curvature
안희갑(Hee-Kap Ahn),배상원(Sang Won Bae),Otfried Cheong 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.2
We consider a point robot in the plane whose turning radius is constrained to be at least 1 and that is not allowed to make reversals. Given a starting configuration (a location and an orientation) for the robot, we give a new geometric proof on the combinatorial structure of curvature-constrained shortest paths to a final point with free orientation.
두 평면 볼록집합의 겹치는 영역을 최대화하는 강체운동을 구하는 근사 알고리즘
박종대(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/ε)) 시간에 구할 수 있다.