기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
구 볼록 다각형 들의 분리 및 교차를 위한 간선 기반 알고리즘의 구현
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 구 볼록 다각형 들의 분리 및 교차를 위한 간선 기반 알고리즘의 구현
저자명
하종성,천은홍,Ha. Jong-Seong,Cheon. Eun-Hong
간행물명
정보과학회논문지. Journal of KIISE. 시스템 및 이론
권/호정보
2001년|28권 9호|pp.479-490 (12 pages)
발행정보
한국정보과학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

본 논문에서는 구상에서 주어진 볼록 다각형의 집합$Gamma$=${P_1...P_n}$의 최대 또는 최소 교차를 결정하기 위하여 다각형의 간선으로 구를 면으로 분할하는 문제를 고려한다. 이 문제는 $Gamma$의 최대 부분집합을 포함하는 반구를 $Gamma$를 분리하는 대원을, $Gamma$를 이분하는 대원을 $Gamma$를 최소 또는 최대 부분집합을 교차하는 대원을 각각 찾는 다섯가지 기하적 문제를 공통적으로 관련이 있다. 구다각형의 최대 및 최소 교차를 효율적으로 구하기 위하여 우리는 간선 기반 분할의 방식을 취하는데 이 방식에서는 구가 각 다각형에 의해 증분적으로 분할되면서 면이 아닌 면을 구성하는 간선의 소유권이 처리된다. 마지막에는 최대수의소유권을 가지는 분할된 비정렬 간선들을 모아 해가 되는 면들의 경계를 구성하지 않고 그들의 중심을 근사적으로 얻는다. 최대 교차를 찾는 우리의 알고리즘은 효율적인 시간복잡도 O(nv)를 가지는 것으로 분석된다. 여기서 n는 v은 각각 다각형과 모든 장점의 개수들이다. 더구나 견고하게 수치를 계산하고 모든 degeneracy 경우를 다루기 때문에 구현의 관점에서도 실제적이다. 유사한 방식을 사용하여 일반적인 교차의 모든 경계는 O(nv+LlogL)시간에 구성할 수 있다. 여기서 L은 해로 출력되는 간선의 개수이다.

기타언어초록

In this paper, we consider the method of partitioning a sphere into faces with a set of spherical convex polygons $Gamma$=${P_1...P_n}$ for determining the maximum of minimum intersection. This problem is commonly related with five geometric problems that fin the densest hemisphere containing the maximum subset of $Gamma$, a great circle separating $Gamma$, a great circle bisecting $Gamma$ and a great circle intersecting the minimum or maximum subset of $Gamma$. In order to efficiently compute the minimum or maximum intersection of spherical polygons. we take the approach of edge-based partition, in which the ownerships of edges rather than faces are manipulated as the sphere is incrementally partitioned by each of the polygons. Finally, by gathering the unordered split edges with the maximum number of ownerships. we approximately obtain the centroids of the solution faces without constructing their boundaries. Our algorithm for finding the maximum intersection is analyzed to have an efficient time complexity O(nv) where n and v respectively, are the numbers of polygons and all vertices. Furthermore, it is practical from the view of implementation, since it computes numerical values. robustly and deals with all the degenerate cases, Using the similar approach, the boundary of a general intersection can be constructed in O(nv+LlogL) time, where : is the output-senstive number of solution edges.