Algorithms for covering and packing and applications to CAD/CAM (abstract only): preliminary results

ABSTRACT

Computational geometry deals with the computational complexity of geometric problems within the framework of the analysis of algorithms. Numerous applications have been found to computer graphics, computer-aided design, pattern recognition and robotics. Among the geometric problems are bin packing problems. C.A. Roger “Packing and Covering”, Cambridge University Press (1964) studied these problems. Many of these are hard problems, and very few have been solved. Some packing problems are the restriction of a very interesting problem in CAM (computer-aided manufacture). In the manufacture of clothing, certain parts, such as sleeves, are laid out as repeated polygonal copies and combinations on a bolt of cloth. This pattern layout is traditionally (and currently) done by hand. It's a candidate for automation. We propose some special cases of this problem whose solution can be extended to practical use. We are working on several geometric questions involving packing translations of objects. Classical results in mathematics demonstrate equivalence between certain packing problems and finding optimal enclosed figures. J. O'Rourke et al [“An optimal algorithm for finding minimal enclosing triangles”, J. of Algorithms 7, 258-264 (1986)], as well as V. Klee and M. Laskowski [“Finding the smallest triangles containing a given convex polygon”, J. of Algorithms 6, 359-375 (1985)] have produced algorithms for finding a smallest area triangle containing (or enclosing) a given polygon. Smallest area convex polygons of a certain type, containing a given set, can be viewed as larger pieces of fabric containing pattern to be cut out. We have an optimal algorithm for finding largest enclosed polygons for a given set. We also have preliminary results for smallest enclosing polygons. These results have theoretical interest, and have applications to robotics and collision avoidance, as well as to manufacture.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

  J. Computer Applications

General Terms:
Algorithms, Design, Performance, Theory