Abstract - We give the first algorithmic study of a class of "covering tour" problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a "cutter" so that it sweeps out a specified region ("pocket"), in order to minimize a cost that depends not only on the length of the tour but also on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. We prove lower bounds (NP-completeness of minimum-turn milling) and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme (PTAS) based on a novel adaptation of the m-guillotine method.
Abstract - We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds? There are several models of simple folds; the simplest one-layer simple fold rotates a portion of paper about a crease in the paper by 180 degrees. We first consider the analogous questions in one dimension lower - bending a segment into a flat object - which lead to interesting problems on strings. We develop efficient algorithms for the recognition of simply foldable 1-D crease patterns, and reconstruction of a sequence of simple folds. Indeed, we prove that a 1-D crease pattern is flat foldable by any means precisely if it is by a sequence of one-layer simple folds. We give several new results on 2-D ``map'' foldings, including a linear-time algorithm for deciding foldability of an orthogonal crease pattern on a rectangular piece of paper, and various hardness results showing that it is (weakly) NP-complete to decide foldability of (1) an orthogonal crease pattern on a rectilinear piece of paper, (2) a crease pattern of axis-parallel and diagonal (45-degree) creases on a square piece of paper, and (3) crease patterns without a mountain/valley assignment.
Abstract - A sculpting package provides the user a set of primitive shapes and a set of operators to operate on them. Voxel based representations are attractive for sculpting due to their ability to work with arbitrary topology with uniform ease. Minkowski operators have been found useful in providing some of the common tools for Interactive Sculpting. This paper gives algorithms for implementing these for voxel grids and octrees.