Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, and Craig S. Kaplan, “Polygons Cuttable by a Circular Saw”, Computational Geometry: Theory and Applications, volume 20, number 1–2, October 2001, pages 69–84. Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.

Abstract:

We introduce and characterize a new class of polygons that models wood, stone, glass, and ceramic shapes that can be cut with a table saw, lapidary trim saw, or other circular saw. In this model, a circular saw is a line segment (in projection) that can move freely in empty space, but can only cut straight into a portion of material. Once a region of material is separated from 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 out of a convex shape of material by a sufficiently small circular saw. We prove that a polygon has this property precisely if it does not have two adjacent reflex vertices. As a consequence, every polygon can be modified slightly 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 that are at most 2.5 times the optimal. We also study polygons cuttable by an arbitrarily large circular saw, which is equivalent to a ray, and give two linear-time recognition algorithms.

Comments:

This paper is also available from ScienceDirect.

Copyright:

The paper is \copyright Elsevier Science B.V.

Length:

The paper is 14 pages.

Availability:

The paper is available in PostScript (424k) and gzipped PostScript (135k).

See information on file formats.

[Google Scholar search]

Related papers:

CCCG2000a (Polygons Cuttable by a Circular Saw)