ISSN:
1432-0541
Keywords:
Key words. Computational geometry, Containment, Approximation, Nesting, Packing, Layout, Marker making.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. We present an algorithm for finding a solution to the two-dimensional translational approximate multiple containment problem: find translations for k polygons which place them inside a polygonal container so that no point of any polygon is more than 2ε inside of the boundary of any other polygon. The polygons and container may be nonconvex. The value of ε is an input to the algorithm. In industrial applications the containment solution acts as a guide to a machine cutting out polygonal shapes from a sheet of material. If ε is chosen to be a fraction of the cutter's accuracy, then the solution to the approximate containment problem is sufficient for industrial purposes. Given a containment problem, we characterize its solution and create a collection of containment subproblems from this characterization. We solve each subproblem by first restricting certain two-dimensional configuration spaces until a steady state is reached, and then testing for a solution inside the configuration spaces. If necessary, we subdivide the configuration spaces to generate new subproblems. The running time of our algorithm is $O(({1}/{\epsilon})^{k} \log ({1}/{\epsilon}) k^6 s \log s) $ , where s is the largest number of vertices of any polygon generated by a restriction operation. In the worst case s can be exponential in the size of the input, but, in practice, it is usually not more than quadratic.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00014415
Permalink