지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술대회자료
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 한국정보과학회 학술발표논문집 한국정보과학회 1994년도 가을 학술발표논문집 제21권 제2호(B)
- 발행연도
- 1994.10
- 수록면
- 655 - 658 (4page)
이용수
초록· 키워드
오류제보하기
화랑문제(Art Gallery Problem)의 한 분야인 경비원 경로 문제는 다각형 내부의 모든 영역을 볼 수 있는 경비원의 이동 경로를 찾는 문제이다. 경비원 경로 문제에 대한 지금까지의 연구는 주로 경로의 길이를 최소화하는데 관심이 있었으나, 본 논문에서는 길이와는 무관하게 링크의 수를 최소로 하는 경로를 구하는 알고리즘을 제시한다. 링크는 경로를 이루는 직선 선분을 말한다.
최소 길이의 경비원 경로는 단순 다각형의 경우, 출발점이 주어진 상태에서 O(n³)에 구할 수 있다. 본 논문에서는 단조 다각형과 소용돌이 다각형(1-소용돌이 다각형, 2-소용돌이 다각형)에 대해 최소 링크를 가지는 경비원 경로를 출발점이 주어지지 않은 상태에서도 각각 O(N²), O(n)에 구하는 알고리즘을 제시한다.
최소 길이의 경비원 경로는 단순 다각형의 경우, 출발점이 주어진 상태에서 O(n³)에 구할 수 있다. 본 논문에서는 단조 다각형과 소용돌이 다각형(1-소용돌이 다각형, 2-소용돌이 다각형)에 대해 최소 링크를 가지는 경비원 경로를 출발점이 주어지지 않은 상태에서도 각각 O(N²), O(n)에 구하는 알고리즘을 제시한다.
목차
요약
1. 서론
2. 용어 정의
3. 최소 링크를 가지는 경로를 구하는 알고리즘
4. 결론
참고문헌
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
단조 다각형에서 최단 경비원 경로를 구하는 최적 알고리즘
한국정보과학회 학술발표논문집
1995 .04
-
단조 다각형에서 최소 링크를 가진 경비원 경로를 구하는 최적 알고리즘
정보과학회논문지(A)
1997 .02
-
약 가시성 다각형에서 최소 링크를 가진 최단 경비원 경로를 구하는 알고리즘
정보과학회논문지 : 시스템 및 이론
2002 .06
-
단조 다각형에서 최소 개수의 링크를 가진 최단 경비원 경로를 구하는 선형 알고리즘
정보과학회논문지(A)
1999 .11
-
단순 다각형을 경비하는 대각 경비원 배치 알고리즘
한국정보과학회 학술발표논문집
1991 .04
-
단조 다각형에서 최단 경비원 경로를 구하는 알고리즘
정보과학회논문지(A)
1996 .03
-
다각형면에서의 보수적 가시성 검사를 위한 영상기반방법
한국정보과학회 학술발표논문집
1997 .10
-
다각형 포함 트리를 구하는 효율적인 알고리즘
한국정보과학회 학술발표논문집
1994 .10
-
선분가시 다각형 내부에 있는 두 점 사이의 최단 경로를 구하는 빠른 알고리즘
한국정보통신학회논문지
2010 .02
-
다각형 교차 문제를 위한 상수 시간 재구성메쉬 알고리즘
정보과학회논문지(A)
1999 .11
-
단순 다각형의 한 에지로 부터의 에지 가시성 다각형을 구하는 최적 알고리즘
한국정보과학회 학술발표논문집
1990 .10
-
약 가시성 다각형에서 최소 링크를 가진 경비원 경로
컴퓨터산업학회논문지
2002 .01
-
자유형상의 파라메트릭 변형을 위한 조정 다각형 생성
한국정보과학회 학술발표논문집
2003 .10
-
일반화 다각형을 위한 plane - sweep 알고리즘의 구현
한국정보과학회 학술발표논문집
2002 .04
-
삼각분할을 이용한 다각형의 형태변환 알고리즘
한국정보과학회 학술발표논문집
1998 .10
-
단순 다각형에서의 대각 가시성 문제에 대한 효율적인 알고리즘
한국정보과학회 학술발표논문집
1993 .10
-
교통망에 적합한 K 비루프 경로 탐색 알고리즘
대한교통학회지
2004 .12
-
병목을 찾는 알고리즘과 그 응용
한국정보과학회 학술발표논문집
1992 .04
-
단순다각형의 최단 외부가시선분을 구하는 최적 알고리즘
한국정보과학회 학술발표논문집
1991 .04
-
두 단순 다각형의 교차 영역을 구하는 상수 시간 RMESH 알고리즘
한국정보과학회 학술발표논문집
1998 .04
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017900237