An Algorithm for the Approximation of Surfaces and for the Packing of Volumes

Abstract

An algorithm is presented here that approximates a given swface A by a set of regular or semi-regular faces forming a polyhedron C. If the faces are all square, C assumes the aspect of a 'blocked' swface. It is also possible to say that C is a swface constructed of only a limited number of possible configurations of edges incident with a vertex. It is shown that if square faces are used, C approximates A within r v3, where r = length of the edge of the square face. The advantages are discussed of describing A numerically rather than analytically. Technical details of the computer procedure adopted with the algorithm are commented upon. The time complexity is given as kme, where e = number of edges in C and m = number of elements descnbing A. Applied to closed surfaces, the algorithm can be used to solve the problem of packing solids in a given volume. For an open swface the algorithm produces a closed C that encloses A on all sides.