지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 시스템 및 이론 정보과학회논문지 : 시스템 및 이론 제28권 제9·10호
- 발행연도
- 2001.10
- 수록면
- 479 - 490 (12page)
이용수
초록· 키워드
오류제보하기
본 논문에서는 구상에서 주어진 볼록 다각형의 집합 Γ＝{P₁,…,Pn}의 최대 또는 최소 교차를 결정하기 위하여 다각형의 간선으로 구를 면으로 분할하는 문제를 고려한다. 이 문제는 Γ의 최대 부분집합을 포함하는 반구를, Γ를 분리하는 대원을, Γ를 이분하는 대원을, Γ를 최소 또는 최대 부분집합을 교차하는 대원을 각각 찾는 다섯 가지 기하적 문제와 공통적으로 관련이 있다.
구다각형의 최대 및 최소 교차를 효율적으로 구하기 위하여 우리는 간선 기반 분할의 방식을 취하는데이 방식에서는 구가 각 다각형에 의해 증분적으로 분할되면서 면이 아닌 면을 구성하는 간선의 소유권이 처리된다. 마지막에는 최대수의 소유권을 가지는 분할된 비정렬 간선들을 모아 해가 되는 면들의 경계를 구성하지 않고 그들의 중심을 근사적으로 얻는다.
최대 교차를 찾는 우리의 알고리즘은 효율적인 시간복잡도 O(nv)를 가지는 것으로 분석된다. 여기서 n과 v은 각각 다각형과 모든 정점의 개수들이다. 더구나 견고하게 수치를 계산하고 모든 degeneracy 경우를 다루기 때문에 구현의 관점에서도 실제적이다. 유사한 방식을 사용하여 일반적인 교차의 모든 경계는 O(nv＋LlogL) 시간에 구성할 수 있다. 여기서 L은 해로 출력되는 간선의 개수이다.
구다각형의 최대 및 최소 교차를 효율적으로 구하기 위하여 우리는 간선 기반 분할의 방식을 취하는데이 방식에서는 구가 각 다각형에 의해 증분적으로 분할되면서 면이 아닌 면을 구성하는 간선의 소유권이 처리된다. 마지막에는 최대수의 소유권을 가지는 분할된 비정렬 간선들을 모아 해가 되는 면들의 경계를 구성하지 않고 그들의 중심을 근사적으로 얻는다.
최대 교차를 찾는 우리의 알고리즘은 효율적인 시간복잡도 O(nv)를 가지는 것으로 분석된다. 여기서 n과 v은 각각 다각형과 모든 정점의 개수들이다. 더구나 견고하게 수치를 계산하고 모든 degeneracy 경우를 다루기 때문에 구현의 관점에서도 실제적이다. 유사한 방식을 사용하여 일반적인 교차의 모든 경계는 O(nv＋LlogL) 시간에 구성할 수 있다. 여기서 L은 해로 출력되는 간선의 개수이다.
목차
요약
Abstract
1. 서론
2. 구상의 기하적 문제의 정의
3. 알고리즘의 개요
4. 구현
5. 시간복잡도 분석과 실험
6. 결론
참고문헌
저자소개
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
구상의 볼록 다각형의 교차 계산을 위한 새로운 간선 전진 기법의 선형 시간 알고리즘
정보과학회논문지 : 시스템 및 이론
2001 .02
-
두 볼록 다각형의 교차 부분을 구하는 알고리즘
한국정보과학회 학술발표논문집
1988 .10
-
다각형 교차 문제를 위한 상수 시간 재구성메쉬 알고리즘
정보과학회논문지(A)
1999 .11
-
단순 다각형의 교차에 관한 알고리즘
(구)정보과학회논문지
1983 .11
-
다각형면에서의 포관 가시성 검사를 위한 영상 기반 방법
정보과학회논문지(A)
1998 .06
-
두 단순 다각형의 교차 영역을 구하는 상수 시간 RMESH 알고리즘
한국정보과학회 학술발표논문집
1998 .04
-
단순 다각형 내부의 두 가시성 다각형에 대한 집합 연산을 수행하는 최적 알고리즘
정보과학회논문지 : 시스템 및 이론
2004 .02
-
삼각분할을 이용한 다각형의 형태변환 알고리즘
한국정보과학회 학술발표논문집
1998 .10
-
직교 다각형을 최소 갯수의 직사각형으로 분할하는 알고리즘
한국정보과학회 학술발표논문집
1988 .10
-
병목을 찾는 알고리즘과 그 응용
(구)정보과학회논문지
1993 .05
-
다각형 포함 트리를 구하는 효율적인 알고리즘
한국정보과학회 학술발표논문집
1994 .10
-
단순 직교 다각형을 최소 갯수의 직교 볼록 다각형으로 분할하는 알고리즘
한국정보과학회 학술발표논문집
1991 .04
-
최소 되먹임 간선 집합 문제 알고리즘
한국컴퓨터정보학회논문지
2015 .03
-
다각형면에서의 보수적 가시성 검사를 위한 영상기반방법
한국정보과학회 학술발표논문집
1997 .10
-
유사 삼각 분할을 이용한 단순 다각형의 형태 변환 알고리즘
정보과학회논문지 : 시스템 및 이론
2000 .11
-
직교 다각형의 내부에 포함되는 최대 직사각형을 구하는 알고리즘
(구)정보과학회논문지
1988 .02
-
단순 다각형의 L₁-중심을 구하는 알고리즘
(구)정보과학회논문지
1988 .12
-
단순 다각형의 집합에서 외부 가시 부분을 구하는 알고리즘
한국정보과학회 학술발표논문집
1991 .04
-
세 다각형을 포함하는 최소 넓이 볼록 헐을 구하는 알고리즘
한국정보과학회 학술발표논문집
2012 .11
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017817508