Sets of lines and cutting out polyhedral objects

Jerzy W. Jaromczyk, Mirosaw Kowaluk

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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 languageEnglish
Pages (from-to)67-95
Number of pages29
JournalComputational Geometry: Theory and Applications
Issue number1-2
StatePublished - May 2003

Bibliographical note

Funding Information:
* Corresponding author. E-mail address: [email protected] (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.


  • 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


Dive into the research topics of 'Sets of lines and cutting out polyhedral objects'. Together they form a unique fingerprint.

Cite this