Rolling discs and their applications

Abstract

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$...