차선거리유지 경로찾기

나현숙,김정희,Na, Hyeon-Suk,Kim, Jung-Hee 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.8

The best coverage problem is finding a path whose worst distance to the sensor-set is the best among all paths. Instead, if the user stays close to its nearest two sensors, then the stability of the wireless connection may be guaranteed. So we consider the problem of finding a second best coverage path; given the sensor set U, a starting point s and a target point t, find a path whose worst distance to the second closest sensor is minimized. This paper presents an O(n logn) -time algorithm to find such a path. We also give experimental evidence showing that the connection to the sensor-set along a second best coverage path is more stable than that along the best coverage path. 사용자가 가능한 센서 가까이에서 이동하는 문제를 최단거리유지 문제(Best Coverage Problem)라 하며, 무선 연결의 안정성을 높이기 위해서 두 개의 센서로부터 최대한 가까이 위치하며 움직이는 이동경로를 차선거리유지 경로(Second Best Coverage Path)라고 한다. 이 논문에서는 센서들의 집합 U와 시작점 s, 끝점 t가 주어질 때, s에서 t까지 이르는 모든 경로 중에서, 가장 가까운 두 개의 센서까지 거리 중 큰 값이 최소가 되는 차선거리유지 경로를 찾는 O(n logn)-시간 알고리즘을 제시하며, 차선거리유지 경로를 따라 움직일 때가 최단거리유지 경로를 따라 움직일 때 보다, 네트워크에의 연결이 보다 안정적임을 보여주는 실험결과도 또한 제시한다.

차선최단거리유지이동경로 찾기

나현숙(Hyeon-Suk Na),김정희(Junghee Kim) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.2B

사용자가 가능한 센서 가까이에서 이동하는 문제를 최단거리유지문제라 하며, 무선 연결의 안정성을 높이기위해서 두 개의 센서로부터 가까이에 위치하여 사용자가 움직이는 이동경로를 차선최단거리유지이동경로라고 한다. 이 논문에서는 주어진 센서들의 집합 U와 시작점 s, 끝점 t가 주어질 때, s에서 t까지 이르는 경로로서, 가장 가까운 두 개의 센서까지의 거리가 최소인 차선최단거리유지이동경로를 찾는 O((c²n+e)log(c²n)-시간 알고리즘을 제시한다. 여기서 c는 집합 U의 하나의 사이트가 갖는 최대 보로노이 선분의 개수이다.

The Tight Upper Bound on the Offline Cop Number

Hyeon-Suk Na(나현숙),Yu-Seok Jo(조유석) 한국정보과학회 2013 정보과학회논문지 : 시스템 및 이론 Vol.40 No.4

지정된 경로를 따라 n×n 격자 그래프를 탐색하는 경찰들이 있다. 도둑은 이들의 경로를 미리 모두 알고 있지만, 경찰은 도둑의 위치에 대해 전혀 알지도 못하고, 경로를 수정할 수도 없다. 그러면 유한한 시간 내에 도둑을 잡기 위해서는 몇 명의 경찰이 필요할까? 이 숫자, 즉 도둑을 잡기위해 필요한 최소의 경찰수를 오프라인 경찰수 라고 한다. 오프라인 경찰수에 대해 알려진 자명한 상한은 n인데, 왜냐하면 n명의 경찰이 일렬횡대로 서서 격자그래프를 바닥부터 천장까지 탐색해간다면 도둑은 어떻게 해도 n 시간 내에 잡힐 수밖에 없기 때문이다. Brass et al. [1]은 교번모델 - 매시간 먼저 경찰이 최대 s(≥1)개의 간선을 이동한 후 도둑이 최대 한 개의 간선을 이동하는 모델 - 에 대해서, 도둑은 언제나 ?n/(s+1)? 명의 경찰을 피할 수 있으며, ?n/(s+1)?+1명의 경찰이 어떠한 도둑도 잡을 수 있도록 하는 탐색경로를 제시했다. 즉, 오프라인 경찰수의 하한이 ?n/(s+1)?+1이고 상한이 ?n/(s+1)?+1 임을 증명했다. 또한 s=1인 경우, ?n/2?+1명의 경찰이 도둑을 잡는 탐색경로를 제시함으로써, s=1인 교번모델의 오프라인 경찰수가 ?n/2?+1임을 보였다. 이 논문에서는 나머지 경우, 즉 s≥ 2인 교번모델에서, ?n/(s+1)?+1명의 경찰이 어떠한 도둑도 잡을 수 있도록 하는 탐색경로를 제시하여 오프라인 경찰수가 ?n/(s+1)?+1임을 보인다. Imagine that cops patrol the n×n grid on fixed routes. The robber has full knowledge of the cops’ routes in advance, but the cops know nothing of the robber’s position and cannot change their routes. Then how many cops are necessary to catch the robber in finite time? This number, the minimum number of cops needed to catch the robber is called the offline cop number. A trivial upper bound is n since n cops standing abreast and sweeping the grid from the bottom to the top will catch any smartest robber within n time in spite of knowing nothing of the robber’s position. In an alternating-move-model where at each time the cops first move (at most) s(≥1) edges at a time and then the robber moves at most one edge, Brass et al. [1] proved a lower bound of ?n/(s+1)?+1 and an upper bound of ?n/(s+1)?+1; they showed that a robber can always escape detection of ?n/(s+1)? cops indefinitely and provided a strategy for ?n/(s+1)?+1 cops to catch the robber. They closed the gap in the case where s=1, by giving a strategy for ?n/2?+1 cops to catch the robber. In this note, we close the gap for the other case where s≥ 2 by presenting a strategy for ?n/(s+1)?+1 cops to catch the robber.

차선거리유지 경로찾기

나현숙(Hyeon-Suk Na),김정희(Junghee Kim) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.7·8

사용자가 가능한 센서 가까이에서 이동하는 문제를 최단거리유지 문제(Best Coverage Problem)라 하며, 무선 연결의 안정성을 높이기 위해서 두 개의 센서로부터 최대한 가까이 위치하며 움직이는 이동경로를 차선거리유지 경로(Second Best Coverage Path)라고 한다. 이 논문에서는 센서들의 집합 U와 시작점 s, 끝점 t가 주어질 때, s에서 t까지 이르는 모든 경로 중에서, 가장 가까운 두 개의 센서까지 거리 중 큰 값이 최소가 되는 차선거리유지 경로를 찾는 ?O(nlogn)-시간 알고리즘을 제시하며, 차선거리유지 경로를 따라 움직일 때가 최단거리유지 경로를 따라 움직일 때 보다, 네트워크에의 연결이 보다 안정적임을 보여주는 실험결과도 또한 제시한다. The best coverage problem is finding a path whose worst distance to the sensor-set is the best among all paths. Instead, if the user stays close to its nearest two sensors, then the stability of the wireless connection may be guaranteed. So we consider the problem of finding a second best coverage path; given the sensor set U, a starting point s and a target point t, find a path whose worst distance to the second closest sensor is minimized. This paper presents an O(nlogn)-time algorithm to find such a path. We also give experimental evidence showing that the connection to the sensor-set along a second best coverage path is more stable than that along the best coverage path.

스텔스 게임 레벨 디자인 툴의 개선

나현숙(Na, Hyeon-Suk),정상혁(Jeong, Sanghyeok),정주홍(Jeong, Juhong) 한국게임학회 2015 한국게임학회 논문지 Vol.15 No.4

스텔스 게임 레벨 디자이너는 다양한 난이도의 흥미로운 게임환경(레벨)을 제작해야 한다. J. Temblay와 공동 연구자들은 이 과정의 자동화를 돕는 Unity-기반 레벨 디자인 툴을 개발했다. 이 툴은 디자이너가 지도에서 경비병의 경로, 속도, 감시 영역, 플레이어의 출발점과 도착점 등 여러 게임 요소들을 입력하면 플레이어가 취할 수 있는 가능한 경로들을 포함한 다양한 시뮬레이션 결과들을 보여준다. 이를 이용해 디자이너는 현재의 게임 요소들이 자신이 의도한 난이도 및 플레이어 경로를 만드는지 실시간으로 확인할 수 있고, 필요한 경우 이들을 조정할 수 있게 되었다. 여기서는 두 가지 면에서 이 툴의 개선점을 제시한다. 첫째, 디자이너가 몇 개의 지점을 입력하면 이 지점들을 포함하는 흥미로운 경비병의 감시 경로를 난이도별로 추천해주는 기능을 추가해서 레벨 디자인 툴로서의 편의성과 유용성을 높였다. 둘째, 기존의 충돌 체크 함수 및 RRT-기반 경로 탐색 함수를 새로운 충돌 체크 함수와 델로네 로드맵-기반 경로 탐색 함수로 대체하여 시뮬레이션 속도를 크게 향상시켰다. In the stealth game design, level designers are to develop many interesting game environments with a variety of difficulties. J. Tremblay and his co-authors developed a Unity-based level design tool to help and automate this process. Given a map, if the designer inputs several game factors such as guard paths and velocities, their vision, and the player's initial and goal positions, then the tool visualizes simulation results including (clustered) possible paths a player could take to avoid detection. Thus with the help of this tool, the designer can ensure in realtime if the current game factors result in the intended difficulties and players paths, and if necessary adjust the factors. In this note, we present our improvement on this tool in two aspects. First, we integrate a function that if the designer inputs some vertices in the map, then the tool systematically generates and suggests interesting guard paths containing these vertices of various difficulties, which enhances its convenience and usefulness as a tool. Second, we replace the collision-detection function and the RRT-based (player) path generation function, by our new collision-check function and a Delaunay roadmap-based path generation function, which remarkably improves the simulation process in time-efficiency.

직선 위에 중심을 갖는 κ-센터를 계산하는 알고리즘 (pp.562-571)

나현숙(Hyeon-Suk Na),신찬수(Chan-Su Shin) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.11·12

이차원 평면에 주어진 점들을 포함하면서 고정된 기울기를 갖는 직선 위에 중심을 갖는 κ개의 디스크를 찾는 데, 최대 디스크의 반지름이 최소가 되는 디스크 집합을 계산하는 문제를 다룬다. This paper considers variants of κ-center problems to find the set of disks with centers on a given (or moving) line with fixed orientation such that the disks contain a given point set and the maximum radius of the disks is minimized.

직교다각형에 대한 지붕의 기하학적 성질

나현숙(Hyeon-Suk Na),신찬수(Chan-Su Shin),안희갑(Hee-Kap Ahn) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

이차원 평면에 직교다각형이 주어져 있을 때, 직교다각형 위에 45도 각도로 기울어진 면들로 구성된 지형 구조인 지붕(roof)을 정의할 수 있다. 본 논문에서는 직교다각형에 대한 지붕의 다양한 기하학적 성질을 살펴본다. 이것은 인공위성으로부터 얻은 건물의 평면도 이미지로부터 3차원 지붕구조를 획득하여 출력함으로써 사실감있는 영상을 제공하는 데 활용될 수 있다.

Distributed Event Detection Algorithm considering Tradeoff between Accuracy and Cost

나현숙(Hyeon-Suk Na),녀뚜안안(Nhu Tuan Anh) 한국정보과학회 2011 정보과학회논문지 : 정보통신 Vol.38 No.2

본 논문에서는 무선 센서 네트워크상의 이벤트 감지 문제를 푸는 동시에, 정확도와 비용간의 trade-off를 조절할 수 있는 이벤트 감지 분산 알고리즘을 제안한다. 제안된 알고리즘은 관심영역에 랜덤하게 분포시킨 많은 수의 센서들로 감시되는 무선 네트워크를 모델로 하며, 센서들은 0/1-센서로서 낮은 성능의 배터리를 가지며, 감시, 통신, 그리고 아주 간단한 사칙연산만을 수행하는 정도의 극히 제한된 기능성을 갖는다. 이벤트 감지 문제에서는 언제나, 이벤트가 일어나는 순간 그것을 감지하고, 주변의 이웃들에게 이를 알려 그 이상의 이벤트들도 감지할 수 있도록 하는 센서들이 필요하다. 총 파워비용을 줄이거나 모니터링 시간을 최대화하기 위한 스케쥴링 방법들은 광범위하게 연구되어 왔다. 우리의 방법론은 다음과 같다. 일정한 밀도로 분포되도록 미리 선택한 센서들-여기서는 critical sensor라고 부름-은 언제나 깨어있도록 하고, 이들이 이벤트를 감지하면 이를 주변의 이웃들에게 알려 각자의 감지영역을 체크하도록 메시지를 전송한다. 메시지를 받은 센서들은 자신의 감지영역을 체크하고 어떤 조건들을 만족하는지 여부에 따라 깨어날 것인지 계속 sleeping 모드에 있을 것인지를 결정한다. 각 센서에서 실행되는 이 알고리즘은 매우 간단하며 필요에 따라 기껏해야 2 bit의 메시지를 전송하게 된다. 제안된 알고리즘에서 각 센서들은 주어진 네트워크에 의해 초기에 결정되는 하나의 정보-통신 반경 내 센서의 개수 혹은 이웃의 수-를 제외하고는, GPS 정보나 이웃들로부터의 상대적인 위치정보나 거리 등과 같은 정보들은 전혀 이용하지 않는다. 이 알고리즘의 또 하나의 장점은 위에서 설명한 “wake-up 모드가 되기 위한 어떤 조건”에 사용되는 두 가지 역치값들의 적용에 있는데, 이 역치값들을 조절함에 의해서, 우리는 이벤트 감지의 정확도와 통신 비용간의 trade-off를 조종할 수 있기 때문이다. In this paper, we present a distributed algorithm for detecting events in wireless sensor network that provides trade-off between detection accuracy and costs. Our model is that the region of interest is monitored by a large number of randomly distributed 0/1 sensors with low-power battery, limited functionality and memory, just enough for sensing, communicating and performing simple arithmetic operations. For any event detection problem, one needs some sensors awake to detect the event at the time that it happens, and to wake up its neighbors to detect further events. Scheduling for the network to save the total power-cost or to maximize the monitoring time has been studied extensively. Our scheme is that some predetermined uniformly distributed sensors, called critical sensors, are awake all the time and when a critical sensor detect any event, it broadcasts to the neighbors to check their sensing area. Then the neighbors check their area and decide with certain criteria whether they wake up or remain in sleeping mode . This algorithm running in each sensor is very simple and uses at most 2 bit of broadcasting. Sensors do not need any information such as GPS data or the relative position from the neighbors, but the number of its communication neighbors which is initially determined when the network is set. Another advantage of our algorithm is that we adapt two kinds of measure for the wake-up decision. By adjusting the threshold values, our algorithm can be applied for many applications because these thresholds provide trade-off between the accuracy of event detection and the cost of energy and communication.

A Note on Kruskal's Theorem

이계식,나현숙,Lee, Gyesik,Na, Hyeon-Suk Korean Association for Logic 2012 論理硏究 Vol.15 No.3

프리드먼에 의해 제안된 "크루스칼 정리의 소형화 정리"가 2차 페아노 공리체계의 부분 시스템인 $(\prod_{2}^{1}-BI)_0$에서 증명될 수 없음을 증명한다. 또한 위 증명이 크루스칼 정리와 관련된 기존의 연구에서 알려진 중요한 정리들을 잘 조합함으로 해서 가능함을 보인다. It is demonstrated that there is a simple, canonical way to show the independency of the Friedman-style miniaturization of Kruskal's theorem with respect to $(\prod_{2}^{1}-BI)_0$. This is done by a non-trivial combination of some well-known, non-trivial previous works concerning directly or indirectly the (proof-theoretic) strength of Kruskal's theorem.

적응적 다중 시드 영역 확장법을 이용한 구조적 패턴의 보도 영역 검출

원선희,주성일,나현숙,최형일,Weon, Sun-Hee,Joo, Sung-Il,Na, Hyeon-Suk,Choi, Hyung-Il 한국정보처리학회 2012 정보처리학회논문지B Vol.19 No.4

본 논문에서는 보행자에 장착된 카메라로부터 입력된 자연영상에서의 구조적 패턴 변화에 강인한 적응적인 보도 영역 검출 기법을 제안한다. 제안하는 방법에서는 다양한 패턴을 가지는 보도 환경에서 안정적으로 보도 영역을 분할하기 위해 첫 번째 단계에서는 소실점에 기반하는 VRay를 이용한 방사형 영역 분할법을 통해 보도의 경계선을 검출하여 보도의 후보영역을 분리하며, 두 번째 단계에서는 분리된 후보영역 내에서의 시드 영역 확장법(SRG)을 개선한 적응적 다중 시드 영역 확장법(A-MSRG)를 통해 구조적 패턴이 반복되는 보도 영역을 실시간으로 검출하는 방법을 수행한다. 성능평가를 위해 제안된 방사형 영역 분할법과 A-MSRG와의 결합에 의한 영역 검출 결과의 효율성을 측정한다. 기존의 SRG, MSRG 방법과의 비교 수행을 통해 제안된 방법의 타당성을 입증하였다. In this paper, we propose an adaptive pavement region detection method that is robust to changes of structural patterns in a natural scene. In order to segment out a pavement reliably, we propose two step approaches. We first detect the borderline of a pavement and separate out the candidate region of a pavement using VRays. The VRays are straight lines starting from a vanishing point. They split out the candidate region that includes the pavement in a radial shape. Once the candidate region is found, we next employ the adaptive multi-seed region growing(A-MSRG) method within the candidate region. The A-MSRG method segments out the pavement region very accurately by growing seed regions. The number of seed regions are to be determined adaptively depending on the encountered situation. We prove the effectiveness of our approach by comparing its performance against the performances of seed region growing(SRG) approach and multi-seed region growing(MSRG) approach in terms of the false detection rate.