Algorithm of Sequential Improving the Size Coefficient for Solving the Problem of Partitioning the Multiple Connected Orthogonal Polygon
- DOI
- 10.2991/itids-19.2019.24How to use a DOI?
- Keywords
- problem of geometrical partitioning, multiple connected orthogonal polygon, size coefficient, primary partition, composite united, minimization of joints length partition
- Abstract
Abstract—The problem of geometrical partitioning the multiple connected orthogonal polygon is considered in the given paper. The problem refers to the NP-hard class of problems because it is necessary to fulfill exhaustive search for assured finding the optimal solution. It stipulates the interest for developing efficient heuristic methods for solving the above problem. Some multiply-connected orthogonal polygon is supposed to be parted into a set of rectangles avoiding their intersecting and their crossing the polygon borders. The goal function represents certain minimization of summarized length of boundary junctions in the process of partitioning. The mathematical model of the problem is offered. The algorithm based on improving the size coefficient, characterizing the degree of rectangle elongation, has been developed. The algorithm consists of two procedures applied sequentially: the first one is for generating the primary polygon partitioning, and the second is for primary partitioning transformation taking into account the adjacent elements and the compound adjacent elements. The computing experiment has been carried out and the results are shown.
- Copyright
- © 2019, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Anna Filippova AU - Yuliya Valiahmetova AU - Emil Tukhvatullin AU - Elina Dyaminova PY - 2019/05 DA - 2019/05 TI - Algorithm of Sequential Improving the Size Coefficient for Solving the Problem of Partitioning the Multiple Connected Orthogonal Polygon BT - Proceedings of the 7th Scientific Conference on Information Technologies for Intelligent Decision Making Support (ITIDS 2019) PB - Atlantis Press SP - 129 EP - 134 SN - 1951-6851 UR - https://doi.org/10.2991/itids-19.2019.24 DO - 10.2991/itids-19.2019.24 ID - Filippova2019/05 ER -