In this thesis, the notion of a rolling disc which arises from the pocketing problem in NC machining is introduced and characterized. First, We present an O(n log n) algorithm for finding the largest rolling disc of a simple polygon P using the Voronoi diagram of P where n is the number of the vertices of P. This algorithm leads to efficient algorithms for several well-known geometric problems. Second, as an application of the rolling discs, we consider a problem for finding the minimum Euclidean distance between two disjoint simple polygons. This problem can be formulated as computing the largest rolling disc between the two polygons P and Q. We present an O((n + m)log(n + m)) algorithm for solving the minimum distance problem using the largest rolling disc between them, where m is the number of the vertices of Q. Third, as an another application of the rolling discs, the pocketing problem is considered. The pocketing is a machining operation that removes all the material within a given boundary. We present an efficient pocketing algorithm using the notion of a rolling disc of a simple polygon. The largest rolling disc implies the cutter of maximum diameter which does not overcut the stock while machining a pocket. We describe an O(n log n + kn) algorithm for pocketing a simple polygon, where k is the number of contour curves in a pocket P. Fourth, We consider an offsetting problem for a monotone polygon. We propose a linear algorithm for finding an offset of a monotone chain by rolling a disc to the monotone chain. And then, also a linear time algorithm is presented for finding an offset (tool path) of a monotone polygon. Fifth, we generalize the rolling disc to a convex polygon. That is, we formulate the generalized rolling discs and propose an O((log$^2$k)n log n) algorithm for finding the largest generalized rolling disc, which represented by a convex polygon, of a simple polygon. We can also find the generalized rolling disc in L$_1$ metric and L$_\infty$ metric by a convex polygon which is a square tipped $45^\circ$ and a square, respectively.
본 논문에서는 NC 밀링 기계의 포켓 커팅(pocket cutting) 문제로 부터 생겨난 롤링 디스크를 정의하고 그의 특성을 보였고, 이와 관계있는 여러가지 기하학적인 문제들을 다루었다. 롤링 디스크(rolling disc)란 단순 다각형의 외부와 만나지 않고 다각형의 모든 에지를 방문할 수 있는 디스크이다. 본 논문에서는 롤링 디스크가 여러가지 기하학적인 문제를 해결하는데 있어서 유용한 도구로 사용될 수 있음을 보였다. 먼저 Voronoi diagram을 이용하여 다각형 P의 최대 크기의 롤링 디스크를 찾는 O(nlogn) 알고리즘을 제시하였다. 최대크기의 롤링 디스크는 포켓 커팅에 있어서 대강 깍아내는데 필요한 도구(tool)의 크기를 의미한다. 또한 최대크기의 롤링 디스크는 두개의 서로 교차하지 않는 다각형 사이의 최소거리를 구하는 문제에 응용 될 수 있다. 이는 두 다각형 사이를 지나갈 수 있는 최대크기의 롤링 디스크를 구하는 문제로 두 다각형 사이의 영역을 단순 다각형으로 나타내는 방법을 제시하여 두 다각형 사이의 최소거리를 O(n log n)시간에 구하는 알고리즘을 제시하였다. 다음으로 본 논문의 동기가된 포켓 커팅 문제를 해결하는 알고리즘을 제시하였다. 포# ? 커팅은 주어진 경계(boundary)의 내부를 도구를 이용하여 깍아내는 작업으로 NC 밀링 기계에서 빈번하게 사용되는 작업중의 하나이다. 포켓 커팅은 포켓 내부를 깍아내는 도구의 경로를 구하는 문제인데 일반적으로 도구는 디스크로 모델링 될 수 있다. 본 연구에서는 다각형의 경계를 따라 움직이는 도구의 경로를 구하는 contour-parallel 방식에 대해 다루었다. 롤링 디스크의 개념을 이용하여 단순 다각형으로 나타내어지는 모양의 내부를 깍아내는O(n log n + kn) 알고리즘을 제시 하였다. 단, k는 다각형 P의 contour curve의 수이다. 또한, 단순 다각형의 모양이 제한적일 경우의 도구경로를 구하는 문제를 다루었다. Monotone 다각형의 경우 O(n) 시간에 하나의 contour curve를 구하는 알고리즘을 제시하였다. Monotone 다각형은 두개의 monotone chain으로 나누어지고 또한 monotone chain의 도구경로도 monotone한 성질을 이용하여 monotone chain에 롤링 디스크를 굴려서 O(n)에 하나의 contour curve를 구하였다. 마지막으로 롤링 디스크의 일반화에 대해 연구하였다. 디스크의 모양이 원이 아닌 볼록(convex) 다각형인 경우의 최대크기 롤링 디스크 문제에 대해 고려하였다. 이 문제thⓟ 주어진 볼록 다각형에의해 정의되는 convex-distance 함수에 의한 일반화한 Voronoi diagram으로 구해질 수 있었고, 볼록 다각형의 모양이 내부의 각이 90$^\circ$인 마름모인 경우에는 $L_1$ - metric의 롤링 디스크이고, 볼록 다각형의 모양이 정사각형인 경우에는 $L_\infty$ - metric의 롤링 디스크가 된다.
