Heuristics for estimating contact area of supports in layered manufacturing

Ivayio Ilinkin, Ravi Janardan, Michiel Smid, Eric Johnson, Paul Castillo, Jörg Schwerdt

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Layered manufacturing is a technology that allows physical prototypes of three-dimensional(3D) models to be built directly from their digital representation, as a stack of two-dimensional(2D) layers. A key design problem here is the choice of a suitable direction in which the digital model should be oriented and built so as to minimize the area of contact between the prototype and temporary support structures that are generated during the build. Devising an efficient algorithm for computing such a direction has remained a difficult problem for quite some time. In this paper, a suite of efficient and practical heuristics is presented for estimating the minimum contact area. Also given is a technique for evaluating the quality of the estimate provided by any heuristic, which does not require knowledge of the (unknown and hard-to-compute) optimal solution; instead, it provides an indirect upper bound on the quality of the estimate via two relatively easy-to-compute quantities. The algorithms are based on various techniques from computational geometry, such as ray-shooting, convex hulls, boolean operations on polygons, and spherical arrangements, and have been implemented and tested. Experimental results on a wide range of real-world models show that the heuristics perform quite well in practice.

Original languageEnglish (US)
Article number1210589
JournalACM Journal of Experimental Algorithmics
StatePublished - 2006


  • Algorithm implementation and testing
  • Algorithms
  • Computational geometry
  • E.1 [Data structures]
  • Experimentation
  • F.2.2 [Analysis of algorithms and problem complexity]: Nonnumerical algorithms and problems
  • I.6 [Computer-aided engineering]
  • Measurement
  • Performance
  • Theory

Fingerprint Dive into the research topics of 'Heuristics for estimating contact area of supports in layered manufacturing'. Together they form a unique fingerprint.

Cite this