약 가시성 다각형에서 최소 링크를 가진 경비원 경로

류상률 한국컴퓨터산업학회 2002 컴퓨터産業敎育學會論文誌 Vol.3 No.1

주어진 다각형의 내부를 경로를 따라 이동하면서 감시하는 경비원 경로는 길이의 최소화 또는 링크의 최소화 등으로 구분할 수 있다. 최소링크를 가진 경비원 경로(watchman route with minimum route)는 경로의 방향 전환 횟수가 최소인 경비원 경로이며, 약 가시성 다각형(weakly visible polygon)은 서로 약 가시성을 가진 두개의 체인으로 구성된 다각형이다. 본 논문에서는 n개의 꼭지점을 가진 약 가시성 다각형의 최소 링크를 가진 경비원 경로를 구하는 Ο($n^2$) 시간의 알고리즘을 제시한다. The watchman routes which an watchman patrols the interior of given polygon moving along the route are classified to minimum length or minimum links. The watchman route with minimum links has minimum changes of direction and a weakly visible polygon consists of two chains which have mutually weakly visibility. In this paper, we present an Ο($n^2$) time algorithm for finding the watchman route with minimum links in the weakly visible polygons, where n is the number of vertices of a given polygon.

약 가시성 다각형에서 최소 링크를 가진 최단 경비원 경로를 구하는 알고리즘

류상률 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.6

A weakly visible polygon is an n-gon in the plane and consists of two mutually weakly visible chains. In this paper, we present an O(n2) time algorithm that finds a shortest watchman route among the routes with minimum links where a watchman patrols the inside of weakly visible polygons. 2차원 평면상에 n개의 꼭지점을 가지며 서로 약 가시적인 2개의 체인으로 구성된 다각형을 약 가시적 다각형이라 한다. 본 논문에서는 약 가시적 다각형의 내부를 감시하는 최소 링크를 가진 경비원 경로들 중에서 최소 길이를 가지는 경비원 경로를 O(n2) 시간에 구하는 알고리즘을 제시한다.

약 가시성 다각형에서 최소 링크를 가진 최단 경비원 경로를 구하는 알고리즘

류상률,Ryu, Sang-Ryul 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5

2차원 평면상에 n개의 꼭지점을 가지며 서로 약 가시적인 2개의 체인으로 구성된 다각형을 약 가시적 다각형이라 한다. 본 논문에서는 약 가시적 다각형의 내부를 감시하는 최소 링크를 가진 경비원 경로들 중에서 최소 길이를 가지는 경비원 경로를 $O(n^2)$ 시간에 구하는 알고리즘을 제시한다. A weakly visible polygon is an n-gon in the plane and consists of two mutually weakly visible chains. In this paper, we present an $O(n^2)$ time algorithm that finds a shortest watchman route among the routes with minimum links where a watchman patrols the inside of weakly visible polygons.

특성 다각형에서 최소링크의 경비원 경로를 구하는 알고리즘

류상률,Ryu, Sang-Ryul 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.4

다각형의 내부를 경로를 따라 이동하면서 감시하는 경비원 경로는 길이 또는 링크의 최소화 등으로 구분할 수 있다. 최소링크의 경비원 경로(watchman route with minimum route)는 경로 진행에서 발생하는 방향 전환의 횟수가 최소인 경비원 경로이다. 본 논문에서는 특성 다각형인 약 가시 다각형(weakly visible polygon)에서 최소링크의 경비원 경로를 구하는 $O(N^2)$시간 알고리즘을 제시한다. The watchman routes which an watchman patrols the interior of polygon moving along the route are classified to minimum length or minimum links. The watchman route with minimum links has minimum changes of direction in process. In this paper, we present an algorithm with $O(N^2)$ time for finding the watchman route with minimum links in the weakly visible polygons which have specific property.

단조 다각형에서 최소 링크를 가진 경비원 경로를 구하는 최적 알고리즘

류상률(Sangryul Ryu),김승호(Sung-Ho Kim) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.2

다각형 내부의 경비원 경로(watchman route)는 경로 상에서 다각형 내부의 점들을 모두 볼 수 있는 경로이며, 최소 링크를 가진 경비원 경로(watchman route with minimum link)는 최소 개수의 선분으로 구성된 경로이다. 본 논문에서는 2차원 평면에서 임의의 선분에 단조적인 2개의 체인(chain)으로 구성되며 n개의 꼭지점을 가진 단조(monotone) 다각형의 최소 링크를 가진 경비원 경로를 구하는 O(n) 시간 복잡도와 O(n) 공간 복잡도의 최적 알고리즘을 제시한다. A watchman route in a polygon is a polygonal path that each point in the interior of the polygon is visible from at least one point along the route and a minimum-link watchman route has minimum number of lines to farm the route. In this paper, we present an optimal algorithm with O(n) time and O(n) space that finds a minimum-link watchman route in a monotone polygon which consists of n vertices and is a union of two monotone chains with respect to a line segment in the plane.

단순 직교 다각형을 최소 갯수의 직교 볼록 다각형으로 분할하는 알고리즘

류상률(Ryu Sangryul),박덕진(Park Deokjin),김승호(Kim Sungho) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.1

본 논문에서는 원 그래프의 최대 독립 집합을 이용하여 단순 직교 다각형을 최소갯수의 직교 볼록다각형으로 분할하는 알고리즘을 제시한다. 직교 다각형의 peak들을 시계방향으로 원주상에 표현하여 만든 원 그래프(Circle Graph)를 보 그래프(Complement Graph)로 변형시킨후, 이의 최대 클릭(Maximum Clique)을 이용한 모든 최대 독립 집합을 구하므로써 다각형 내부에 steiner point를 허용하지 않으면서 모든 peak를 제거한 직교 볼록 다각형으로 분할하였다. 제시한 알고리즘의 시간복잡도는 O(n⁴)이다.

단조 다각형에서 최단 경비원 경로를 구하는 최적 알고리즘

류상률(Sang-Ryul Ryu),김승호(Sung-Ho Kim) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

경비원 경로(shortest watchman route) 문제는 계산 기하학(computational geometry)의 가시성(visibility) 분야에서 중요하게 다루고 있는 문제이다. 다각형에서 최단 경비원 경로는 경로상에서 다각형 내부의 점들을 모두 볼 수 있는 최단 경로이다. n개의 절점으로 구성된 단순(simple) 다각형의 경우에는 다각형 내부의 한 점 s가 경비원 경로의 출발점으로 주어졌을 때 최단 경비원 경로에 근사한 경비원 경로를 구하는 O(n⁴) 시간 복잡도의 알고리즘이 제시되어 있다. 임의의 선분 l에 단조적인 2개의 체인(chain)으로 구성될 수 있는 다각형을 단조(monotone) 다각형이라 한다. 본 논문에서는 n개의 절점으로 구성된 단조 다각형의 최단 경비원 경로를 구하는 O(n) 시간 복잡도와 O(n) 공간 복잡도를 가진 최적(optimal) 알고리즘을 제시한다.

단조 다각형에서 최단 경비원 경로를 구하는 알고리즘

류상률(Sang-Ryul Ryu),서대화(Dae-Hwa Seo),김승호(Sung-Ho Kim) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.3

다각형 내부의 최단 경비원 경로(shortest watchman route)는 경로 상에서 다각형 내부의 점들을 모두 볼 수 있는 최단 경로이다. 본 논문에서는 2차원 평면상에서 임의의 선분 l에 단조적이며 n개의 꼭 지점을 가진 2개의 체인(chain)으로 구성되는 단조 다각형(monotone polygon)의 최단 경비원 경로를 구하는 O(n) 시간과 O(n) 공간 복잡도의 알고리즘을 제시한다. The shortest watchman route in a polygon is the shortest route such that each point in the interior of the polygon is visible from at least one point along the route. In this paper, we present an O(n) time and O(n) space algorithm that find the shortest watchman route in a monotone polygon, which consists of n vertices and is a union of two chains with respect to l in the plane.

모바일 컴퓨팅 환경기반의 u-Campus 구성원 중심의 취업 서비스 모델

류상률(Ryu, Sang-Ryul),김혁진(Kim, Hyeock-Jin),이세열(Lee, Se-Yul) 한국산학기술학회 2008 한국산학기술학회논문지 Vol.9 No.5

최근 대학의 교육 환경은 교육 여건과 IT 인프라의 발전을 기반으로 많은 변화를 가져오고 있다. 특히 대학의 경쟁력 제고와 대학 이미지 개선을 목표로 중장기 발전계획을 도모하고 있다. 이를 실현하기 위한 단계적인 과정으로 유비쿼터스 캠퍼스를 구축하고 있으며, 교육 서비스의 확대와 IT 기술의 발전을 기반으로 다양한 서비스를 위한 콘텐츠 시스템을 구축하고 있다. 현재 구축되고 있는 서비스 환경은 실수요자들 위한 효율적인 서비스가 제공되지 못하고 있으며, 신기술의 도입이나 연구개발을 통한 테스트베드의 성격이나 원활한 서비스 운영에만 집중되어 있다. 또한 급변하는 대한 환경에서 새롭게 요구되고 있는 교육 콘텐츠 서비스에 대한 구성원 중심의 최적화된 모델을 구현하는데 한계가 있다. 본 논문에서는 대학 구성원 중심의 효율적인 유비쿼더스 캠퍼스 취업 서비스 모델을 제시한다. 제시한 모텔을 기반으로 유비쿼터스 캠퍼스 구축의 핵심요소인 구성원 중심의 U-리쿠르트, 캠퍼스 안내 모바일 서비스 등을 통하여 구성원이 실질적으로 필요로 하는 콘텐츠를 제공하는 유비쿼터스 캠퍼스 서비스 모델을 구성할 수 있다. Recently, the university environment has been changed faster than before. It has based on university environment and IT infrastructure. Especially, most of local university has devised development plan such as improving the image and competitive power of campus. Digital , Electronic and Mobile Campus has increased the importance as people realize that the use of technology can improve the learning process. U-Campus of latest IT Technology need a service environment of which the practical use is possible through IT analysis of the members. For example u-campus setup of mobile offers the convenience to the members. We expected thing to use much, even though actual condition investigation about IT environment of the user is insufficient. The inconvenience of mobile could not be activated to the service for proactive use. The importance became the result about u-campus service setup of a company and university center. This service environment cannot offer specific information of center members for which the service implements. In this paper, we studied about members centralized u-campus model through u-recruit, campus information mobile service on university.

단조 다각형에서 최소 개수의 링크를 가진 최단 경비원 경로를 구하는 선형 알고리즘

류상률(Sang-Ryul Ryu) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.11

n개의 꼭지점을 가진 단조(monotone) 다각형은 2차원 평면상의 임의의 선분에 단조 적인 2개의 체인으로 구성된다. 단조 다각형의 내부를 경로 상에서 모두 감시할 수 있는 최소 링크를 가진 경비원 경로(watchman route with minimum links)는 최소 개수의 선분으로 구성된 경로로서 하나 이상 존재할 수 있다. 본 논문에서는 단조 다각형의 최소 링크를 가진 경비원 경로들 중에서 최단 경비원 경로를 구하는 O(n) 시간의 알고리즘을 제시한다. A monotone polygon consists of n vertices and is a union of two monotone chains with respect to some line segment in the plane. A watchman route with minimum-links is a polygonal path such that each point in the interior of the polygon can be visible from at least one point along the route. There may be more than one watchman route with minimum links for given monotone polygon. In this paper, we present an algorithm with O(n) time that finds a shortest watchman route among the watchman routes with minimum links in a monotone polygon.