Near optimal-partitioning of rectangles and prisms.
Prosenjit K. Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Kriz̧anc, Dominic Lessard · 1999
This paper focuses on the following problems: Problem 1 Given an axis parallel rectangle, how do you cut it in k equal area pieces such that the total length of the cuts is minimum? What are the properties of an optimal cut? Problem 2 Given an axis parallel prism, how do you cut it in k equal volume pieces such that the total surface area of the cuts is minimum? What are the properties of an optimal cut? The problems depend on how the cuts are made. Although cuts may take a general form, in this paper we restrict our attention to straight line cuts and planar cuts. We assume that each cut is complete in that it divides a rectangle or a prism into two pieces (such a cut is often referred to in the literature as a glass cut or a guillotine cut)