Computation of pair placement of geometric objects (Q5954749)

This paper is devoted to the problem of two-dimensional placement of pair of polygons with sides parallel to the coordinate axes according to the criterion of maximum intersection area. An algorithm is developed for determining an optimal placement of a pair of orthoblocks with \(m\) and \(n\) vertices. The time and space complexity bounds of the algorithm are \(O({m^2}{n^2}(m+n)\log(m+n))\) and \(O(mn)\). Approximate algorithms for the problem are proposed.