## Abstract

We study algorithmic questions related to cutting polyhedral shapes with a hot wire cutter. Such cutters are popular manufacturing tools for cutting expanded polystyrene (styrofoam) with a thin, moving heated wire. In particular, we study the question of polyhedral-wise continuity: Can a given object be cut out without disconnecting and then reattaching the wire? In an abstract setting this question translates to properties of sets of lines and segments and therefore becomes suitable for computational geometry techniques. On the combinatorial and algorithmic levels the results and methods are related to two problems: (1) given a set F={f _{1},...,f _{k}} of polygons and a polygon f, decide if there is a subset of lines in the set of lines not stabbing F that cover f; (2) construct the connectivity graph for free movements of lines that maintain contact with the polyhedral shape. Problem (1) is solved with the dual projection and arrangements of convex and concave x-monotone curves. Problem (2) can be solved with a combination of the skewed projections [6] and hyperbola arrangements proposed by McKenna and O'Rourke [11]. We provide an O(n ^{5}) algorithm for constructing a cutting path, if it exists. The complexity of the algorithm is determined by the O(n ^{4}) size of the connectivity graph and the cost of solving (2).

Original language | English |
---|---|

Pages (from-to) | 67-95 |

Number of pages | 29 |

Journal | Computational Geometry: Theory and Applications |

Volume | 25 |

Issue number | 1-2 |

DOIs | |

State | Published - May 2003 |

### Bibliographical note

Funding Information:* Corresponding author. E-mail address: jurek@cs.engr.uky.edu (J.W. Jaromczyk). 1 Partially supported by grant KBN 8T11C03915. This research was partially supported by the Center for Computational Sciences of the University of Kentucky.

## Keywords

- Dual projection
- Hot-wire cutting
- Manufacturing
- Polyhedral objects
- Skewed projection

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics