Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC machining

Prosenjit Gupta, Ravi Janardan, Jayanth Majhi, Tony Woo

Research output: Contribution to journalArticlepeer-review

44 Scopus citations


In 4- and 5-axis NC machines, the time to dismount, recalibrate, and remount the workpiece after each set of accessible faces of the workpiece has been machined can be considerable in comparison to the actual machining time. Unfortunately, the problem of minimizing the number of set-ups is NP-hard. In this paper, efficient algorithms are given for a greedy heuristic, where the goal is to find an orientation for the workpiece which maximizes the number of faces that can be machined in a single setup - using either a ball-end or a fillet-end cutter. The algorithms are based on geometric duality, topological sweep, interesting new properties concerning intersection and covering on the unit-sphere, and on techniques for efficiently constructing and searching an arrangement of polygons on the unit-sphere. The results imply that the optimal number of set-ups can be approximated to within a logarithmic factor. Evidence is also provided that it may not be possible to improve substantially on the proposed algorithms.

Original languageEnglish (US)
Pages (from-to)577-587
Number of pages11
JournalCAD Computer Aided Design
Issue number8
StatePublished - Aug 1996


  • Arrangements
  • Computational geometry
  • Duality
  • NC machining
  • Spherical polygons
  • Topological sweep
  • Visibility map
  • Workpiece set-up


Dive into the research topics of 'Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC machining'. Together they form a unique fingerprint.

Cite this