본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.29 no.5, 2002년, pp.274 - 283   피인용횟수: 1

약 가시성 다각형에서 최소 링크를 가진 최단 경비원 경로를 구하는 알고리즘
An algorithm for finding a shortest watchman route with minimum links in the weakly visible polygons

류상률   (청운대학교 컴퓨터과학과UU0001256  );
  • 초록

    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.


  • 주제어

    경비원 경로.  

  • 참고문헌 (25)

    1. 류상률, '단조 다각형에서 최단 경비원 경로를 구하는 최적 알고리즘,' 경북대학교 박사학위 논문, 1998 
    2. 유관희, 좌경룡, 신성용, '단순 직교 다각형에서 직교 거리 문제에 관한 선형 시간 알고리즘,' 정보 과학회 논문지 제 23권 제 6호, pp. 573-579, 1996 
    3. 이상호, 문지영, '두 동적 감시자의 감시 체인에 관한 문제', 정보 과학회 논문지 제20권 제9호, pp. 1252-1262, 1993 
    4. 류상률, 서대화, 김승호, '단조 다각형에서 최단 경비원 경로를 구하는 알고리즘,' 정보과학회 논문지 제23권 제3호, pp. 244-258, 1996 
    5. 류상률, 김승호, '단조 다각형에서 최소링크를 가진 경비원 경로를 구하는 최적 알고리즘,' 정보과학회 논문지 제24권 제2호, pp. 122-130, 1997 
    6. X. H. Tan, T. Hirata, 'Constructing shortest watchman routes by divide and conquer,' Proc. 4th Intern. Symp. on Algorithms and Computation, pp. 68-77, Springer Verlag, 1993 
    7. S. Y. Shin, 'Visibility in the plane and its related problems,' Ph.D. dissertation, Michigan Univ., 1986 
    8. S. Suri, 'On some link distance problems in a simple polygon,' IEEE Trans. Robotics and Automation, vol, 6, pp. 108-113, 1990 
    9. W. Lenhart, R. Pollack, J. R. Sack, R. Seidel, M. Sharir, S. Suri, G. Toussaint, S. Whitesides, and C. Yap, 'Computing the link center of a simple polygon,' Discrete Comput. Geom., Vol. 3, pp. 281-293, 1988 
    10. B. J. Nilsson, Guarding Art Galleries-Methods for Mobile Guards, Ph. D. thesis, Lund Univ., 1995 
    11. J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987 
    12. J. O'Rourke, 'An alternative proof of the rectilinear art gallery theorem,' J. of Geometry, Vol. 21, pp. 118-130, 1983 
    13. S. H. Lee, K. Y. Chwa, 'Some chain visibility problems in simple polygon,' Algorithmica, Vol. 5, pp. 485-507, 1990 
    14. C. Icking and R. Klein, 'The two guards problem,' Proc. 7th ACM Symp. on Computational Geometry, pp. 166-175, 1991 
    15. J. Kahn, M. Klawe, and D. Kleitman, 'Traditional galleries require fewer watchman,' SLAM J. Alg. Disc. Meth., Vol. 4, pp. 194-206, 1983 
    16. S. H. Kim, Visibility algorithms under distance constraint, Ph.D. dissertation, Korea Advanced institute of Science and technology, 1994 
    17. H. Edelsbrunner, J. O'Rourke, and E. Welzl, 'Stationing guards in rectilinear art galleries,' Comput. vision, Graphics, and Image Process. Vol. 28, pp. 167-176, 1984 
    18. P. J. Heffernan,'An optimal algorithm for the two guard problem,' Proc. 9th ACM Symp. on Computational Geometry, pp. 348-358, 1993 
    19. L. J. Guibas and J. Hershberger, 'Optimal shortest path queries in a simple polygon,' Proc. 3rd ACM Symposium on Computational Geometry, Waterloo, pp. 50-63, 1987 
    20. J. I. Doh and K. Y. Chwa, 'An algorithm for determining internal line visibility of a simple polygon,' Report no. CS-TR-88-33, Korea Advanced Institute of Science and Technology, 1988 
    21. W. P. Chin;S. Ntafos, 'Shortest watchman routes in simple polygons,' Discrete Comput. Geometry, Vol. 6, pp. 9-31, 1991 
    22. V. Chvatal, 'A combinatorial theorem in plane geometry,' J. Combin. Thoery ser. B, Vol. 18, pp. 39-41, 1975 
    23. W. P. Chin and S. Ntafos, 'Optimum watchman route,' Info. Proc. Lett., vol. 28, pp. 39-44, 1988 
    24. Y. J. Chiang and R. Tammasia, 'Optimum shortest path and minimum link path queries between two convex polygons inside a simple polygonal obstacle,' Info. Proc. Lett., vol. 28, pp. 39-44, 1994 
    25. A. Aggarwal, The art gallery theorem : its variatiions, applications, and algorithmic aspects, Ph.D. thesis, Johns Hopkins Univ., 1984 
  • 이 논문을 인용한 문헌 (1)

    1. Ryu, Sang-Ryul 2002. "An algorithm for finding a watchman route with minimum links in the characteristic polygons" 정보처리학회논문지. The KIPS transactions. Part A. Part A, a9(4): 595~602     

 저자의 다른 논문

  • 류상률 (9)

    1. 1999 "단조다각형에서 최소 개수의 링크를 가진 최단 경비원경로를 구하는 선형 알고리즘" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (11): 1437~1445    
    2. 2002 "Quadtree를 사용한 색상-공간 특징과 객체 MBR의 질감 정보를 이용한 영상 검색" 정보과학회논문지. Journal of KISS : Computing practices. 컴퓨팅의 실제 8 (6): 692~704    
    3. 2002 "특성 다각형에서 최소링크의 경비원 경로를 구하는 알고리즘" 정보처리학회논문지. The KIPS transactions. Part A. Part A a9 (4): 595~602    
    4. 2002 "약 가시성 다각형에서 최소 링크를 가진 경비원 경로" 컴퓨터산업학회논문지 = Journal of the Korea Computer Industry Society 3 (1): 35~44    
    5. 2008 "모바일 컴퓨팅 환경기반의 u-Campus 구성원 중심의 취업 서비스 모델" 한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society 9 (5): 1296~1303    
    6. 2009 "비정상 트래픽 분석과 퍼지인식도를 이용한 NePID 설계" 한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society 10 (4): 811~817    
    7. 2012 "ON CONVERGENCES FOR ARRAYS OF ROWWISE PAIRWISE NEGATIVELY QUADRANT DEPENDENT RANDOM VARIABLES" Journal of applied mathematics & informatics 30 (1): 327~336    
    8. 2012 "H.264/AVC에서 향상된 인트라/인터 예측을 위한 모드 추정 방법" 한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society 13 (4): 1830~1838    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기