Proceedings of the 7th Scientific Conference on Information Technologies for Intelligent Decision Making Support (ITIDS 2019)

<Previous Article In Volume
Next Article In Volume>

Algorithm of Sequential Improving the Size Coefficient for Solving the Problem of Partitioning the Multiple Connected Orthogonal Polygon

Authors
Anna Filippova, Yuliya Valiahmetova, Emil Tukhvatullin, Elina Dyaminova
Corresponding Author
Anna Filippova
Available Online May 2019.
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/).

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the 7th Scientific Conference on Information Technologies for Intelligent Decision Making Support (ITIDS 2019)
Series
Advances in Intelligent Systems Research
Publication Date
May 2019
ISBN
10.2991/itids-19.2019.24
ISSN
1951-6851
DOI
10.2991/itids-19.2019.24How to use a DOI?
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

risenwbib
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  -