http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
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.
안희갑(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.
박용희(Yong-Hee Park),배상원(Sang Won Bae),안희갑(Hee-Kap Ahn),좌경룡(Kyung-Yong Chwa) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.2Ⅰ
본 논문에서는 코어를 이용한 주조에 대한 계산 기하학 문제를 다룬다. 주조는 녹인 물질을 주형 안에 주입해서 응고시킨 후 주형을 제거하는 방법으로, 주물은 주형의 내부 공동의 모양을 갖게 된다. 코어는 두 개의 주형으로는 만들 수 없는 물체를 주조하기 위한 부속물로서, 두 개의 주요 주형이 제거되는 방향과는 다른 방향으로 제거된다. 따라서 코어를 사용하면 두 개의 주형으로는 제작할 수 없는 물체를 주조로 만들 수 있게 된다. 본 논문에서는 어떤 물체가 주어졌을 때, 코어를 사용하는 주조로 만들 수 있는지를 증명할 수 있는 필요충분 조건을 제시한다. 또한, 다면체의 물체를 테스트하는 O(n³log n)의 알고리즘과, 동일한 시간안에 주형의 형태를 만들어낼 수 있는 알고리즘을 제시한다.
김상섭(Sang-Sub Kim),안희갑(Hee-Kap Ahn) 한국정보과학회 2011 한국정보과학회 학술발표논문집 Vol.38 No.1B
이 논문에서는 2차원 평면에서 n개의 구들이 주어졌을 때, 모든 구들이 C₁ ∪ C₂ 에 포함되면서 크기가 가장 작고 합동인 구 C₁, C₂ 를 계산하는 문제에 대해 연구한다. 이 논문에서는 기본적인 방법을 사용하여 O(n?)?시간을 사용하고 O(n) 공간을 쓰는 알고리즘을 제시한다. 또한 우리는 decision 문제를 이용한 이분검색 방법을 사용하는 개선된 알고리즘을 제시한다. 이 알고리즘은 O(n³log²n)의 시간을 사용하고 O(n) 공간을 사용한다.