Inner Approximation of Polygons and Polyhedra by Unions of Boxes
Christian Spielberger, Martin Held · 2006
Given a multiply-connected polygonal area P in the plane and a point set S ⊂ R2, where some points of S may lie inside of P, we present a fast approximation method for finding a largest axis-aligned or oriented rectangle contained in P which does not contain any points of S. All standard meanings of “largest” are supported, such as maximum area and maximum perimeter. This heuristic is extended to finding k rectangles whose union is largest. Furthermore, we present an extension of our method to 3D, i.e., to computing inner approximations of polyhedra (possibly with holes, voids and cavities) by unions of (oriented) boxes. Our 2D algorithm is based on a discretization of space by means of a regular mesh of size w ×h and on a discretization of the rotation angles. Let n be the sum of the number of vertices of P and the number of points in S. Then an inner approximation by k rectangles is found in O ( mn(w + h) + k2k (mwh) k) time and O(wh + n) space, where m denotes the number of rotation angles tested. A similar bound is obtained for the 3D case. Several algorithmic improvements help to decrease the time complexity in practice considerably, thus making it quite feasible to determine inner approximations of complex objects by several boxes within a few seconds of CPU time. Extensive practical tests have yielded a formula for predicting a mesh resolution suitable for achieving the approximation quality sought by a user.