Browse Prior Art Database

Area Minimization Under Geometric Constraints

IP.com Disclosure Number: IPCOM000041574D
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Wolfe, PS: AUTHOR

Abstract

This article concerns a geometric problem relative to area minimization of packaging. A rectangle is to be subdivided into certain subrectangles, which may be further subdivided, etc. The "topology" of the subdivisions is given, but the dimensions are not; they are algebraic unknowns, related by a system of algebraic linear relations describing the topology. The "cells" -- subrectangles which are not further subdivided -- are to have lower bounds on their width, height, and area. The problem posed is that of choosing dimensions for all the rectangles so that the area of the original rectangle is minimized. We denote by x1,..,xn and y1,..,yn, respectively, the widths and heights of all the rectangles, and suppose that the given relationships x > L, y> M, Ax+By=C defining the acceptable sizes, where x=(x1,..,xn), y=(y1,..

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 1

Area Minimization Under Geometric Constraints

This article concerns a geometric problem relative to area minimization of packaging. A rectangle is to be subdivided into certain subrectangles, which may be further subdivided, etc. The "topology" of the subdivisions is given, but the dimensions are not; they are algebraic unknowns, related by a system of algebraic linear relations describing the topology. The "cells" -- subrectangles which are not further subdivided -- are to have lower bounds on their width, height, and area. The problem posed is that of choosing dimensions for all the rectangles so that the area of the original rectangle is minimized. We denote by x1,..,xn and y1,..,yn, respectively, the widths and heights of all the rectangles, and suppose that the given relationships x > L, y> M, Ax+By=C defining the acceptable sizes, where x=(x1,..,xn), y=(y1,..,yn), and the matrices A,B and vectors C,L,M are of appropriate size. Nonlinear constraints of the form xjyj> a, constituting a lower bound for the area of a rectangle, can be handled by a standard device of mathematical programming: rewritten log x + log y > log a, each variable involved in a logarithm can be replaced by a sum of bounded variables, and each logarithm replaced by an appropriate weighted sum of those variables. The result is a piecewise linear approximation to the nonlinear constraint, which can be chosen to be as accurate an approximation as is needed. (This technique is explained in Chapter 6 of the IBM Ma...