Computation of pair placement of geometric objects

MaRDI QIDQ5954749zbMATH OpenFDO

Authors V. N. Martynchik, N. N. Metel'skij, Jean Marie Proth

Publication date 13 September 2002

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

combinatorial algorithmcomplexitymaximum intersection areaoptimal pair placementpolygon

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4051003
• Local optimization method in placement problems of polygons
• An algorithm for polygon placement using a bottom-left strategy
• scientific article; zbMATH DE number 1822170
• Optimal placement of rectangles on a plane with fixed objects

Cited in

(1)

• Computing pairings using x-coordinates only

This page was built for publication: Computation of pair placement of geometric objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5954749)