초록 ▼

기하학적 물체 내의 두 점은 그들을 연결하는 선분이 그 물체 내에 완전히 포함될 때 서로 가시하다고 말한다. 가시성이란 개념은 기본적인 기하학적 성질이다. 이것은 도형 처리 문제의 계산학적 측면의 구조를 이해하는 데 도움을 줄 뿐만 아니라, 이 문제를 풀기 위한 효율적인 알고리즘의 개발에도 기여할 경우가 많다. 본 보고서에서는, 우선 가시성에 따른 계층 구조 모델을 제안하고 이 계층 구조에 따라 다각형을 분류하는 알고리즘을 소개한다. 마지막으로 세가지 알려진 기하학적 문제, 즉 켄벳스 헐 문제, 삼각 분할 문제 및 최단 경로

기하학적 물체 내의 두 점은 그들을 연결하는 선분이 그 물체 내에 완전히 포함될 때 서로 가시하다고 말한다. 가시성이란 개념은 기본적인 기하학적 성질이다. 이것은 도형 처리 문제의 계산학적 측면의 구조를 이해하는 데 도움을 줄 뿐만 아니라, 이 문제를 풀기 위한 효율적인 알고리즘의 개발에도 기여할 경우가 많다. 본 보고서에서는, 우선 가시성에 따른 계층 구조 모델을 제안하고 이 계층 구조에 따라 다각형을 분류하는 알고리즘을 소개한다. 마지막으로 세가지 알려진 기하학적 문제, 즉 켄벳스 헐 문제, 삼각 분할 문제 및 최단 경로 문제를 통하여 가시성이 효율적인 도형 처리에 어떻게 공헌하는 가를 보여준다.

Abstract ▼

Two points in a geometric object are said to be visible each other if the line segment joining them is completely contained in the object. The notion of visibility is a fundamental geometric property. It not only helps understanding the computational structure of geometric problems but also often le

Two points in a geometric object are said to be visible each other if the line segment joining them is completely contained in the object. The notion of visibility is a fundamental geometric property. It not only helps understanding the computational structure of geometric problems but also often leads to efficient algorithms for solving them. In this report, a visibility hierarchy of polygons is first proposed, and then efficient algorithms for classifying a polygon within the framework of the visibility hierarchy are introduced. Finally, through well-known geometric problems such as convex hull problems, triangulation problems, and shortest path problems, how the notion algorithms is demonstrated.

목차 Contents

• 목 차...5
• 제 1 장 연구 배경...7
• 제 2 장 정의 및 표기 방법...15
• 제 3 장 가시성의 계층 구조...21
• 제 4 장 가시성의 결정...34
• 제 5 장 도형 처리 알고리즘과 가시성...47
• 제 6 장 결론...60
• 인용 문헌...61