제한된 분지수를 가지는 최소지름 신장트리

안희갑,신찬수 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.1

이차원 평면에 주어진 n개의 점을 연결하는 신장트리(spanning tree) 중에서, 지름이 최소가 되는 트리는 특정 점에서의 분지수(degree)가 n-1까지 증가할 수 있다. 신장트리가 실제 네트워크 구조로 사용된다면 높은 분지수를 갖는 노드에선 작업 집중현상이 발생하여 전체 네트워크의 성능을 저하시킬 수 있다. 따라서 작은 분지수와 작은 지름을 갖는 트리를 구성하는 것은 중요하다. 본 논문에서는 (1) 트리의 분지수를 자유롭게 조정할 수 있고, (2) 트리의 지름이 최소 지름보다 상수 배 이상 크지 않고, (3) 임의의 점을 루트로 정하여 트리를 구하더라도 항상 단조(monotone)하며, (4) 트리의 에지들이 서로 교차하지 않는 신장트리 구성 알고리즘을 제안한다. 여기서 트리가 단조하다는 것은 루트부터 시작하여 임의의 노드까지 연결되는 경로 위에 있는 점은 루트로부터의 유클리디언 거리가 단순 증가하는 것을 의미한다. 이 단조성은 신장트리를 가시화 할 때의 중요한 미적 기준으로 사용될 수 있다. Given a set S of n points in the plane, a minimum-diameter spanning tree(MDST) for the set might have a degree up to n-1. This might cause the degradation of the network performance because the node with high degree should handle much more requests than others relatively. Thus it is important to construct a spanning tree network with small degree and diameter. This paper presents an algorithm to construct a spanning tree for S satisfying the following four conditions: (1) the degree is controled as an input, (2) the tree diameter is no more than constant times the diameter of MDST, (3) the tree is monotone (even if arbitrary point is fixed as a root of the tree) in the sense that the Euclidean distance from the root to any node on the path to any leaf node is not decreasing, and (4) there are no crossings between edges of the tree. The monotone property will play a role as an aesthetic criterion in visualizing the tree in the plane.

제한된 곡률을 갖는 최단경로에 대한 기하학적 증명

안희갑,배상원,정지원 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.4

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. 이동하는 자동차와 같은 로봇은 이동방향을 변경할 때 제한된 곡률(curvature)로 서서히 방향을 바꿀 수밖에 없다. 본 논문은 물체의 동선의 곡률이 제한되어 있을 경우, 한 구성에서 출발하여 목표점에 이르는 최단경로는 CC 혹은 CS 타입(C는 원호(circular arc), S는 선분(line segment)을 의미한다), 혹은 이들의 부분문자열 타입이 된다는 사실을 기하학적 성질만을 이용하여 증명하였다. 본 연구결과를 이용하여, 시작점 구성에서 출발하여 목표점, 혹은 목표다각형에 도달하는 최단경로는 다각형의 공간복잡도의 선형시간에 계산 가능하다.

제한된 분지수를 가지는 최소지름 신장트리

안희갑,신찬수 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.2

Given a set S of n points in the plane, a minimum-diameter spanning tree(MDST) for the set might have a degree up to n-1. This might cause the degradation of the network performance because the node with high degree should handle much more requests than others relatively. Thus it is important to construct a spanning tree network with small degree and diameter. This paper presents an algorithm to construct a spanning tree for S satisfying the following four conditions: (1) the degree is controled as an input, (2) the tree diameter is no more than constant times the diameter of MDST, (3) the tree is monotone (even if arbitrary point is fixed as a root of the tree) in the sense that the Euclidean distance from the root to any node on the path to any leaf node is not decreasing, and (4) there are no crossings between edges of the tree. The monotone property will play a role as an aesthetic criterion in visualizing the tree in the plane. 이차원 평면에 주어진 n개의 점을 연결하는 신장트리(spanning tree) 중에서, 지름이 최소가 되는 트리는 특정 점에서의 분지수(degree)가 n-1까지 증가할 수 있다. 신장트리가 실제 네트워크 구조로 사용된다면 높은 분지수를 갖는 노드에선 작업 집중현상이 발생하여 전체 네트워크의 성능을 저하시킬 수 있다. 따라서 작은 분지수와 작은 지름을 갖는 트리를 구성하는 것은 중요하다. 본 논문에서는 (1) 트리의 분지수를 자유롭게 조정할 수 있고, (2) 트리의 지름이 최소 지름보다 상수 배 이상 크지 않고, (3) 임의의 점을 루트로 정하여 트리를 구하더라도 항상 단조(monotone)하며, (4) 트리의 에지들이 서로 교차하지 않는 신장트리 구성 알고리즘을 제안한다. 여기서 트리가 단조하다는 것은 루트부터 시작하여 임의의 노드까지 연결되는 경로위에 있는 점은 루트로부터의 유클리디언 거리가 단순 증가하는 것을 의미한다. 이 단조성은 신장트리를 가시화할 때의 중요한 미적 기준으로 사용될 수 있다.

일반적 환경에서 다면체의 castability

안희갑(H.K. Ahn),O. Schwarzkopf(O. Schwarzkopf) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.1A

주조란 제조할 물체의 모양을 따라 만든 주형 사이로 용융액을 부어 넣고 용융액이 굳어진 후 주형을 제거하여 원하는 물체를 얻는 제조공정을 말한다. 우리는 여기서 두 부분으로 구성된 주형을 사용하고 주형의 제거에 관련한 기하학적인 문제를 다룬다. 우리가 다룰 기하학적인 문제는 다면체와 방향 ^→d가 주어졌을 때 다면체에 대한 주형을 , 서로 그리고 다면체와 충돌하지 않고 하나는 ^→d 방향으로 다른 하나는 -^→d 방향으로 이동하여 제거되는, 두 부분으로 분할할 수 있는가 여부이다. 본 논문은 일반적 환경에서 다면체의 castability의 개념을 제시하고 castability와 monotonicity의 관계를 다룬다. 반대방향 주형제거의 경우 두 edges가 주어진 방향과 평행한 공통평면상에 존재할 수 있도록 허용한다. 또한 공통 평면상에 인접하지 않는 faces를 가진 3차원 다면체의 castability에 대해서도 다룬다. 주어진 방향과 수직인 평면상으로 투영된 두 silhouette edges의 cross를 castability의 새로운 조건으로 제시한다.

제한된 곡률을 갖는 최단경로에 대한 기하학적 증명

안희갑(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.

제한된 분지수를 가지는 최소지름 신장트리 (pp.78-85)

안희갑(Heekap Ahn),신찬수(Chan-Su Shin) 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.1·2

이차원 평면에 주어진 n개의 점을 연결하는 신장트리(spanning tree) 중에서, 지름이 최소가 되는 트리는 특정 점에서의 분지수(degree)가 n-1까지 증가할 수 있다. 신장트리가 실제 네트워크 구조로 사용된다면 높은 분지수를 갖는 노드에선 작업 집중현상이 발생하여 전체 네트워크의 성능을 저하시킬 수있다. 따라서 작은 분지수와 작은 지름을 갖는 트리를 구성하는 것은 중요하다. 본 논문에서는 (1) 트리의 분지수를 자유롭게 조정할 수 있고, (2) 트리의 지름이 최소 지름보다 상수 배 이상 크지 않고, (3) 임의의 점을 루트로 정하여 트리를 구하더라도 항상 단조(monotone)하며, (4) 트리의 에지들이 서로 교차하지 않는 신장트리 구성 알고리즘을 제안한다. 여기서 트리가 단조하다는 것은 루트부터 시작하여 임의의 노드까지 연결되는 경로위에 있는 점은 루트로부터의 유클리디언 거리가 단순 증가하는 것을 의미한다. 이 단조성은 신장트리를 가시화할 때의 중요한 미적 기준으로 사용될 수 있다. Given a set S of n points in the plane, a minimum-diameter spanning tree(MDST) for the set might have a degree up to n-1. This might cause the degradation of the network performance because the node with high degree should handle much more requests than others relatively. Thus it is important to construct a spanning tree network with small degree and diameter. This paper presents an algorithm to construct a spanning tree for S satisfying the following four conditions: (1) the degree is controled as an input, (2) the tree diameter is no more than constant times the diameter of MDST, (3) the tree is monotone (even if arbitrary point is fixed as a root of the tree) in the sense that the Euclidean distance from the root to any node on the path to any leaf node is not decreasing, and (4) there are no crossings between edges of the tree. The monotone property will play a role as an aesthetic criterion in visualizing the tree in the plane.

동적 기하 환경에서의 최근접 이웃 탐색 알고리즘

안희갑(Hee-Kap Ahn),정재훈(Mook Kwon Jung),정묵권(Jaehoon Chung) 한국정보과학회 2024 정보과학회지 Vol.42 No.2

제한된 분지수를 갖는 최소 지름 신장 트리 (pp.806-808)

안희갑(Heekap Ahn),한요섭(Yo-Sub Han),신찬수(Chan-Su Shin) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A

이차원 평면에 주어진 n 개의 점을 연결하는 신장 트리(spanning tree) 중에서, 지름이 최소가 되는 최소지름 신장 트리는 특정 점에서의 분지수가 n-1 까지 증가할 수 있다. 본 논문에서는 트리의 분지수(degree)를 입력으로 받아 그 분지수를 넘지 않는 신장 트리를 구성하면서 트리의 지름은 최소 지름의 상수 배를 넘지 않도록 하는 구성 방법을 제안한다.

직사각형 장애물을 피하는 선분 최단경로

서찬양,안태훈,안희갑 한국정보과학회 2023 정보과학회논문지 Vol.50 No.3

본 논문에서는 평면 상에 주어진 n개의 좌표축에 평행한 직사각형 장애물들과 두 개의 좌표축에 평행한 선분에 대해, 장애물을 피하는 두 선분 사이의 L1최단경로를 계산하는 문제를 다룬다. 두 선분 사이의 경로는 각 선분에서 점을 한 개씩 택할 때, 선택된 두 점 사이의 최단경로로 정의된다. 점의 선택 기준에 따라 두 선분 사이의 경로는 다양하게 정의될 수 있다. 우리는 그 중 최단경로의 길이가 최소가 되는 최소 최단경로와, 길이가 최대가 되는 최대 최단경로를 구하는 알고리즘을 제시한다. 본 논문에서는 최소 최단경로를 O(nlogn) 시간에 계산하는 알고리즘과 최대 최단경로를 O(n2) 시간에 계산하는 알고리즘을 제시한다.