Discretization of Geometric Models

Authors

  • Arthur J. Keyan Institute for Informatics and Automation Problems of NAS RA

Keywords:

Optimal cutting of materials, Two - dimensional modeling, Packing problem

Abstract

We are interested in 2D cutting and packing problem with irregularly shaped objects. In previous work the author has presented the description of the two - dimensional modeling program of irregularly shaped objects. The next step of achieving the optimal arrangement of any irregular shape details on the surface is the discretization of geometric models. In this paper a solution to this problem is given. The solution is described in steps.

References

F. Chung, M. Garey and D. Johnson, “On packing two-dimensional bins”, SIAM J. Alg. Disc. Meth., vol. 3, no. 1, pp. 66–76, 1982.

A. Caprara, “Packing 2-dimensional bins in harmony”, Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 490–499, 2002.

N. Bansal, A. Caprara and M. Sviridenko, “A new approximation method for set covering problems with applications to multidimensional bin packing”, SIAM J. Comput. vol. 39, no. 4, pp. 1256–1278, 2009.

A. M. Chwatal and S. Pirkwieser, “Solving the two-dimensional bin-packing problem with variable bin sizes by greedy randomized adaptive search procedures and variable neighborhood search”, EUROCAST, vol. 1, pp. 456-463, 2011.

F. Eisenbrand, D. Palvoelgyi and T. Rothvoss, “Bin packing via discrepancy of permutations”, Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, pp. 22-25, 2011.

A. Layeb and S. Chenche, “A novel grasp algorithm for solving the bin packing problem”, International Journal of Information Engineering and Electronic Business (IJIEEB), vol. 4, no. 2, pp. 8-14, 2012.

G. Perboli, R. Tadei and M. M. Baldi, “The stochastic generalized bin packing problem”, Discrete Applied Mathematics, vol. 160, no. 7-8, pp. 1291—1297, 2012.

M. M. Baldi, T. G. Crainic, G. Perboli and R. Tadei, “Branch-and-price and beam search algorithms for the generalized bin packing problem”, CIRRELT, Montreal, Canada, pp. 1--18, 2012.

A. Keyan, “Modeling of irregularly shaped two – dimensional objects”, Transactions of the IPIA of the NAS RA, Mathematical Problems of Computer Science, vol.44, pp. 154--160, 2015.

Downloads

Published

2021-12-10

How to Cite

Keyan, A. J. . (2021). Discretization of Geometric Models. Mathematical Problems of Computer Science, 45, 99–105. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/172

Issue

Vol. 45 (2016): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.