Earticle

초록

영어

Given art gallery with vertices, the maximum (sufficient) number of mobile guards isfor simple polygon andfor simple orthogonal polygon. However, there is no polynomial time algorithm for minimum number of mobile guards. This paper suggests polynomial time algorithm for the minimum number of mobile guards. Firstly, we obtain the visibility graph which is connected all edges if two vertices can be visible each other. Secondly, we select vertex with and with in and delete visible edges from and incident edges. Thirdly, we select in partial graphs and select edges that is the position of mobile guards. This algorithm applies various art galley problems with simple polygons and orthogonal polygons art gallery. As a results, the running time of proposed algorithm is linear time complexity and can be obtain the minimum number of mobile guards.

한국어

개의 정점으로 구성된 화랑 에 대한 최대 이동 경비원 수는 단순 다각형은, 직각 다각형은이며, 최소 경비원수를 구하는 다항시간 알고리즘은 알려져 있지 않아 NP-난제 (NP-Hard)이다. 본 논문은 화랑 문제의 최소 이동 경비원 수를 구하는 다항시간 알고리즘을 제안하였다. 첫 번째로, 모든 정점에서 볼 수 있는 다른 정점으로 간선을 그린 가시성 그래프를 얻는다. 두 번째로 인 정점 와 에 있는 정점 를 선택하고 가시성 간선과 부속 간선을 삭제한다. 세 번째로, 남아 있는 부분 그래프 각각에 대해 정점 를 선택하여 이동 경비원이 위치할 간선을 선택하였다. 제안된 알고리즘을 다양한 단순 다각형과 직각 다각형 화랑 문제에 적용한 결과 선형시간으로 최소 이동 경비원 수를 얻었다.

목차

요약
 Abstract
 I. 서론
 II. 화랑 경비원 수 문제
 III. 화랑 문제의 최소 이동 경비원수 알고리즘
 IV. 알고리즘 적용 결과 분석
 V. 결론
 참고문헌

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원，강릉원주대학교，멀티미디어공학과 ]
• 최명복 [ Myeong-Bok Choi | 종신회원， 강릉원주대학교 멀티미디어공학과 ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380