Polygons cuttable by a circular saw

We introduce and characterize a new class of polygons that models wood, sto ne, glass and ceramic shapes that can be cut with a table saw, lapidary tri m saw, or other circular saw. In this model, a circular saw is a line segme nt (in projection) that can move freely in empty space, but can only cut st raight into a portion of material. Once a region of material is separated f rom the rest, it can be picked up and removed to allow the saw to move more freely. A polygon is called cuttable by a circular saw if it can be cut ou t of a convex shape of material by a sufficiently small circular saw. We pr ove that a polygon has this property precisely if it does not have two adja cent reflex vertices. As a consequence, every polygon can be modified sligh tly to make it cuttable by a circular saw. We give a linear-time algorithm to cut out such a polygon using a number of cuts and total length of cuts t hat are at most 2.5 times the optimal. We also study polygons cuttable by a n arbitrarily large circular saw, which is equivalent to a ray, and give tw o linear-time recognition algorithms. (C) 2001 Elsevier Science B.V. All ri ghts reserved.