본 논문에서는 곡면위의 점들에 대한 Voronoi diagram을 다룬다. Voronoi diagram은 계산 기하학자 (Computational geometer)들이 가장 선호하는 자료구조(Data structure)중의 하나이다. 이것에 대한 연구는 다양한 자연현상과 다양한 상황들속에서 제기될 수 있으며 따라서 과학의 여러분야에서 응용되고 있는 주제이기도 하다. 평면에서의 Voronoi diagram이, 거리와 site의 개념에 대한 다양한 변형들을 가지고 오랜기간 폭넓게 연구되어온 반면에, 다른 기하적 공간에서의 연구는 거의 되어 있지 않다고 할 수 있다. 이 논문은 세부분으로 나뉘어져 있다. 첫부분에서는, 본 연구의 배경과 Voronoi diagram에 대한 연구의 역사를 약간 소개하고 있다. 두번째 부분에서 우리는, 구면 S상의 site들의 집합 X에 대한 3차원 ...
본 논문에서는 곡면위의 점들에 대한 Voronoi diagram을 다룬다. Voronoi diagram은 계산 기하학자 (Computational geometer)들이 가장 선호하는 자료구조(Data structure)중의 하나이다. 이것에 대한 연구는 다양한 자연현상과 다양한 상황들속에서 제기될 수 있으며 따라서 과학의 여러분야에서 응용되고 있는 주제이기도 하다. 평면에서의 Voronoi diagram이, 거리와 site의 개념에 대한 다양한 변형들을 가지고 오랜기간 폭넓게 연구되어온 반면에, 다른 기하적 공간에서의 연구는 거의 되어 있지 않다고 할 수 있다. 이 논문은 세부분으로 나뉘어져 있다. 첫부분에서는, 본 연구의 배경과 Voronoi diagram에 대한 연구의 역사를 약간 소개하고 있다. 두번째 부분에서 우리는, 구면 S상의 site들의 집합 X에 대한 3차원 유클리드 거리에 따라 정의된 구면위의 Voronoi diagram SV(X)에 대해 조사한다. 우리가 아주 커다란 구의 표면에서 살고 있다는 점을 생각하면 이는 차라리 자연스러운 주제이며 상황설정임을 알 수 있다. 우리는, 반전변환(Inversion) 또는 극사영 (Stereographic projection)을 이용하여, 위에서 정의한 구면위의 Voronoi diagram SV(X)와 평면위의 어떤 점들의 집합에 대한 두가지 Voronoi diagram - Voronoi diagram과 Farthest-point Voronoi diagram- 의 합집합간에 어떤 상관관계가 있음을 밝힌다. 그리고, 이 아이디어를 구면의 두개의 극점으로부터의 반전변환 (Inversion) 또는 극사영 (Stereographic projection)을 이용하여 확장시킨다. 정리하면, 우리는 다음의 사실을 증명한다. 평면상의 site들의 집합 (꼭 점일 필요는 없는) 에 대한 Voronoi diagram을 구하는 알고리듬 A가 주어졌을때, 우리는 두번의 반전변환 혹은 극사영과 약간의 glueing을 이용하여, 구면위의 임의의 site (꼭 점일 필요는 없는)들의 집합에 대한 구면상의 Voronoi diagram을 구해낼 수 있다. 게다가, 평면상의 Farthest-site Voronoi diagram 또한 (평면상의) 어떤 변환된 site들에 대한 A의 적용에 의해서구해낼 수 있음을 밝혔다. 세번째 부분에서, 우리는 n개의 점들에 대한 3차원 Voronoi diagram의 복잡도 (Complexity) - 즉, 꼭지점, 선, 면들의 갯수 - 가 최악의 경우 O(n^(2))라는 사실로부터 출발한다. 하지만, 그 점들이, Cube나 구와 같이 적당히 부드럽고 좋은 경계면을 갖는 3차원 영역에서 무작위적이고 서로 독립적으로 또 균일한 분포(Independently Identically Distributed uniformly)로부터 추출되면, 그 복잡도의 기대값이 0(n)으로 떨어진다는 것도 또한, 공공연히 알려져온 사실이라고 할 수있다. 그래서, 우리는 그 점들이 3차원상의 2차원 곡면으로부터 뽑아지면 어떤 일이 벌어지는지를 알아보고자 한다. 그 예로서, 이 논문에서는 그 점들이 볼록 다양체의 곡면으로부터 뽑아질 때의 상황을 연구했다. 우리는, 점들이 볼록 다양체의 곡면으로부터 위와 같은 방법으로 추출되면, 그 Voronoi diagram의 복잡도의 기대값이 0(n)임을 보였다.
본 논문에서는 곡면위의 점들에 대한 Voronoi diagram을 다룬다. Voronoi diagram은 계산 기하학자 (Computational geometer)들이 가장 선호하는 자료구조(Data structure)중의 하나이다. 이것에 대한 연구는 다양한 자연현상과 다양한 상황들속에서 제기될 수 있으며 따라서 과학의 여러분야에서 응용되고 있는 주제이기도 하다. 평면에서의 Voronoi diagram이, 거리와 site의 개념에 대한 다양한 변형들을 가지고 오랜기간 폭넓게 연구되어온 반면에, 다른 기하적 공간에서의 연구는 거의 되어 있지 않다고 할 수 있다. 이 논문은 세부분으로 나뉘어져 있다. 첫부분에서는, 본 연구의 배경과 Voronoi diagram에 대한 연구의 역사를 약간 소개하고 있다. 두번째 부분에서 우리는, 구면 S상의 site들의 집합 X에 대한 3차원 유클리드 거리에 따라 정의된 구면위의 Voronoi diagram SV(X)에 대해 조사한다. 우리가 아주 커다란 구의 표면에서 살고 있다는 점을 생각하면 이는 차라리 자연스러운 주제이며 상황설정임을 알 수 있다. 우리는, 반전변환(Inversion) 또는 극사영 (Stereographic projection)을 이용하여, 위에서 정의한 구면위의 Voronoi diagram SV(X)와 평면위의 어떤 점들의 집합에 대한 두가지 Voronoi diagram - Voronoi diagram과 Farthest-point Voronoi diagram- 의 합집합간에 어떤 상관관계가 있음을 밝힌다. 그리고, 이 아이디어를 구면의 두개의 극점으로부터의 반전변환 (Inversion) 또는 극사영 (Stereographic projection)을 이용하여 확장시킨다. 정리하면, 우리는 다음의 사실을 증명한다. 평면상의 site들의 집합 (꼭 점일 필요는 없는) 에 대한 Voronoi diagram을 구하는 알고리듬 A가 주어졌을때, 우리는 두번의 반전변환 혹은 극사영과 약간의 glueing을 이용하여, 구면위의 임의의 site (꼭 점일 필요는 없는)들의 집합에 대한 구면상의 Voronoi diagram을 구해낼 수 있다. 게다가, 평면상의 Farthest-site Voronoi diagram 또한 (평면상의) 어떤 변환된 site들에 대한 A의 적용에 의해서구해낼 수 있음을 밝혔다. 세번째 부분에서, 우리는 n개의 점들에 대한 3차원 Voronoi diagram의 복잡도 (Complexity) - 즉, 꼭지점, 선, 면들의 갯수 - 가 최악의 경우 O(n^(2))라는 사실로부터 출발한다. 하지만, 그 점들이, Cube나 구와 같이 적당히 부드럽고 좋은 경계면을 갖는 3차원 영역에서 무작위적이고 서로 독립적으로 또 균일한 분포(Independently Identically Distributed uniformly)로부터 추출되면, 그 복잡도의 기대값이 0(n)으로 떨어진다는 것도 또한, 공공연히 알려져온 사실이라고 할 수있다. 그래서, 우리는 그 점들이 3차원상의 2차원 곡면으로부터 뽑아지면 어떤 일이 벌어지는지를 알아보고자 한다. 그 예로서, 이 논문에서는 그 점들이 볼록 다양체의 곡면으로부터 뽑아질 때의 상황을 연구했다. 우리는, 점들이 볼록 다양체의 곡면으로부터 위와 같은 방법으로 추출되면, 그 Voronoi diagram의 복잡도의 기대값이 0(n)임을 보였다.
In this thesis, we deal with Voronoi diagrams for point sites on a surface. Voronoi diagrams belong to the computational geometer's favorite structures. They arise in nature in various situations and have applications in many fields of science. While Voronoi diagrams in the plane have been studied e...
In this thesis, we deal with Voronoi diagrams for point sites on a surface. Voronoi diagrams belong to the computational geometer's favorite structures. They arise in nature in various situations and have applications in many fields of science. While Voronoi diagrams in the plane have been studied extensively using different notions of sites and metrics for a long time, little is known for other geometric spaces. The thesis is split into three parts. In the first part, we introduce some background of our research and a bit of history of researches on Voronoi diagrams. In the second part, we investigate the Voronoi diagram SV(X) of a set of points X on a sphere S with the Euclidean distance on the surface of the sphere. This is a rather natural setting, considering that we are living on the surface of a large sphere. Using inversion or stereographic projection, we show that there exists a correspondence between SV(X) and the union of the Voronoi diagram and farthest-point diagram of a set of points in a plane. We also extend this idea by using two stereographic projections (or inversions) from opposite poles of the sphere. We prove: given an algorithm A to compute the Euclidean Voronoi diagram of a set of sites in the plane (not necessarily points), we can compute the Voronoi diagram of a set of sites on the sphere by two applications of A and a little bit of glueing. Taking it a step further, we show that a farthest-site Voronoi diagram in the plane can be computed as well by applications of A on suitably transformed sites. In the third, we start with the well-known fact that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n^(2)). It is also implicitly known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensiona1 region whose boundary is as reasonably smooth and nice as a cube or sphere, then the expected complexity falls to 0(n). We analyze what happens if the points are chosen from a 2-dimensiona1 surface in 3-dimensiona1 space. As an example, we examine the situation when the points are chosen from the surface of a convex polytope. We prove that the expected complexity of the Voronoi diagram of n points is 0(n) when the points are chosen from the surface of a convex polytope.
In this thesis, we deal with Voronoi diagrams for point sites on a surface. Voronoi diagrams belong to the computational geometer's favorite structures. They arise in nature in various situations and have applications in many fields of science. While Voronoi diagrams in the plane have been studied extensively using different notions of sites and metrics for a long time, little is known for other geometric spaces. The thesis is split into three parts. In the first part, we introduce some background of our research and a bit of history of researches on Voronoi diagrams. In the second part, we investigate the Voronoi diagram SV(X) of a set of points X on a sphere S with the Euclidean distance on the surface of the sphere. This is a rather natural setting, considering that we are living on the surface of a large sphere. Using inversion or stereographic projection, we show that there exists a correspondence between SV(X) and the union of the Voronoi diagram and farthest-point diagram of a set of points in a plane. We also extend this idea by using two stereographic projections (or inversions) from opposite poles of the sphere. We prove: given an algorithm A to compute the Euclidean Voronoi diagram of a set of sites in the plane (not necessarily points), we can compute the Voronoi diagram of a set of sites on the sphere by two applications of A and a little bit of glueing. Taking it a step further, we show that a farthest-site Voronoi diagram in the plane can be computed as well by applications of A on suitably transformed sites. In the third, we start with the well-known fact that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n^(2)). It is also implicitly known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensiona1 region whose boundary is as reasonably smooth and nice as a cube or sphere, then the expected complexity falls to 0(n). We analyze what happens if the points are chosen from a 2-dimensiona1 surface in 3-dimensiona1 space. As an example, we examine the situation when the points are chosen from the surface of a convex polytope. We prove that the expected complexity of the Voronoi diagram of n points is 0(n) when the points are chosen from the surface of a convex polytope.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.