Средства математического моделирования задач покрытия
The article considers theorems which are useful for the mathematical and computer modeling of the covering problems of a compact canonical multiconnected polygonal set with a finite family of convex polygons. Based on peculiarities of a rectangular cover, theorems concerning a partition of the trans...
Saved in:
| Date: | 2008 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/5824 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Средства математического моделирования задач покрытия / Т.Е. Романова, А.В. Кривуля // Доп. НАН України. — 2008. — № 9. — С. 48-52. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860186600502198272 |
|---|---|
| author | Романова, Т.Е. Кривуля, А.В. |
| author_facet | Романова, Т.Е. Кривуля, А.В. |
| citation_txt | Средства математического моделирования задач покрытия / Т.Е. Романова, А.В. Кривуля // Доп. НАН України. — 2008. — № 9. — С. 48-52. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| description | The article considers theorems which are useful for the mathematical and computer modeling of the covering problems of a compact canonical multiconnected polygonal set with a finite family of convex polygons. Based on peculiarities of a rectangular cover, theorems concerning a partition of the translation vector space and an upper bound of the number of local extrema of the Г-function are formulated.
|
| first_indexed | 2025-12-07T18:04:41Z |
| format | Article |
| fulltext |
5. Hrytsyk V., Hrytsyk V. Determining validity and amount of received information under information transfer
methods using corrective codes. – V Symp. modelowanie i symylacja komputerova w technice. – Lodz,
2005. – P. 99–108.
6. Woznicki J. Podstatowe techniki przetwarzania obrazu. – Warszawa: Wydawnictwo komunikacji i Lacznosci,
1996. – P. 261.
Надiйшло до редакцiї 13.03.2008Державний науково-дослiдний iнститут
iнформацiйної iнфраструктури НАН України, Львiв
УДК 519.85
© 2008
Т.Е. Романова, А.В. Кривуля
Средства математического моделирования задач
покрытия
(Представлено членом-корреспондентом НАН Украины Ю.Г. Стояном)
The article considers theorems which are useful for the mathematical and computer modeling
of the covering problems of a compact canonical multiconnected polygonal set with a finite
family of convex polygons. Based on peculiarities of a rectangular cover, theorems concerning
a partition of the translation vector space and an upper bound of the number of local extrema
of the Γ-function are formulated.
Основой математического моделирования задач геометрического проектирования (зада-
чи покрытия [1] и упаковки [2]) является аналитическое описание отношений точечных
множеств в евклидовых пространствах. С этой целью используется метод Φ-функций [3–
5]. Однако при математическом моделировании отношений двумерных ϕ-объектов [3], по
крайней мере один из которых получен в результате пересечения базовых двухсвязных
ϕ-объектов, возникает необходимость построения Φ-функций в виде композиций Φ-функ-
ций базовых объектов [4]. Конструктивным средством аналитического описания отноше-
ний области покрытия и семейства покрывающих объектов является Γ-функция [6]. Вид
Γ-функции зависит от пространственных форм и метрических характеристик покрываю-
щих объектов. В этой связи актуальны исследования такой зависимости для конечного се-
мейства покрывающих прямоугольников, имеющих не обязательно различные метрические
характеристики.
Пусть имеется компактное многосвязное каноническое многоугольное множество Ω ⊂
⊂ R2 и множество P =
τ⋃
s=1
Ps ⊂ R2, где R2 — двухмерное арифметическое евклидово
пространство; Ps =
ns⋃
i=1
Psi, ns 6 n, Psi — выпуклый многоугольник; τ — число компонент
связности множества P . Пусть H =
τ⋂
s=1
Hs, Hs = R2 \ int Ps, int Ps — внутренность Ps. При
этом Hs =
λs⋃
j=1
Csj , где Csj — выпуклое, многоугольное, канонически замкнутое, в общем
случае неограниченное множество.
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №9
В дальнейшем, множество T ⊂ R2, транслированное на вектор w ∈ R2, обозначим T (w).
Теорема 1. Пусть H(w) = R2 \ intP (w) и Φsj(w + wsj, v) — Φ-функция множеств
Csj(w + wsj) и Ω(v), wsj = const, v ∈ R2, j = 1, 2, . . . , λ, s = 1, 2, . . . , τ , тогда функция
Φ(w, v) = max
s=1,...,τ
min
j=1,...,λ
Φsj(w + wsj , v) (1)
является Φ-функцией множеств H(w) и Ω(v).
Пусть имеется семейство Λ = {Pi(ui), i ∈ In = {1, 2, . . . , n}} выпуклых многоугольников
Pi(ui), i ∈ In.
Как известно [6], семейство Λ при ui = const, i ∈ In, является покрытием области Ω(v),
если любая точка z ∈ Ω(v) принадлежит хотя бы одному из Pi(ui), i ∈ In, т. е. выполняется
условие
Ω(v) ⊆ P (w) или Ω(v)
⋂
int H(w) = ∅. (2)
Теорема 2. Если Φ(w, v) — Φ-функция множеств H(w) и Ω(v) вида (1), то
Φ(w, v) > 0 (3)
является критерием покрытия (2) множества Ω(v) семейством Λ.
Замечание. Соотношение (3) можно рассматривать также в качестве условия трансля-
ционного включения (2) при w = const или условия взаимного непересечения множеств
H(w) и Ω(v) в задачах упаковки.
Теорема 3. Пусть Ω =
K⋃
k=1
Ωk, Ωk = conv{ωkj = (x̃kj, ỹkj), j ∈ Imk
}, а Λ — семейство
прямоугольников Pi(ui) = {(x, y) ∈ R2,−ai 6 x−xi 6 ai,−bi 6 y−yi 6 bi}, ui = const, i ∈ In,
и выполняются условия теоремы (1). Тогда справедлива оценка сложности вычисления
Φ-функции (1) для множеств H(w) и Ω(v)
ν = max
l=1,...,4
ξl,
где
ξ1 = 4Kn, ξ2 =
K∑
k=1
(nmk + 8n − mk − 4), ξ3 =
K∑
k=1
(2nmk + 12n − 3mk − 14),
ξ4 =
K∑
k=1
(
1
4
n2mk + nmk + n2 + 8n − 2mk − 12
)
, если n = 2t, t ∈ N,
K∑
k=1
(
1
4
n2mk + nmk + n2 + 8n −
13
4
mk − 19
)
, если n = 2t + 1, t ∈ N.
Теорема 4. Пусть имеется Pi(ui) = {(x, y) ∈ R2,−ai 6 x − xi 6 ai,−bi 6 y − yi 6 bi}
и Pj(uj) = {(x, y) ∈ R2,−aj 6 x − xj 6 aj,−bj 6 y − yj 6 bj}, uij = (ui, uj) ∈ R4, i 6= j.
Тогда разбиение пространства R4 имеет вид
1) R4 =
11⋃
q=1,q 6=2
R
q
ij или R4 =
10⋃
q=1
R
q
ij , если ai 6= aj и bi 6= bj , где
R1
ij = {uij ∈ R4 : Φij(uij) > 0},
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №9 49
R2
ij = {uij ∈ R4 : ft(uij) > 0, ai > aj, bi < bj , t = 1, . . . , 4},
R3
ij = {uij ∈ R4 : ft(uij) > 0, t = 3, 4, ft(uij) > 0, t = 2, 9},
R4
ij = {uij ∈ R4 : ft(uij) > 0, t = 1, 2, ft(uij) > 0, t = 8, 11},
R5
ij = {uij ∈ R4 : ft(uij) > 0, t = 3, 4, ft(uij) > 0, t = 5, 10},
R6
ij = {uij ∈ R4 : ft(uij) > 0, t = 1, 2, ft(uij) > 0, t = 7, 12},
R7
ij = {uij ∈ R4 : ft(uij) > 0, t = 6, 8, 9, 11},
R8
ij = {uij ∈ R4 : ft(uij) > 0, t = 6, 7, 9, 12},
R9
ij = {uij ∈ R4 : ft(uij) > 0, t = 5, 7, 10, 12},
R10
ij = {uij ∈ R4 : ft(uij) > 0, t = 5, 8, 10, 11},
R11
ij = {uij ∈ R4 : ft(uij) > 0, ai < aj, bi < bj , t = 1, . . . , 4},
R
q
ij = intR
q
ij , q = 1, 2(11), R
q
ij = cl Rq
ij , q = 7, 8, 9, 10,
R
q
ij 6= intR
q
ij , R
q
ij 6= cl Rq
ij , q = 3, 4, 5, 6, в пространстве R4;
2) R4 =
⋃
q=1,3,5,7,8,9,10
R
q
ij , если ai = aj и bi 6= bj , где
R1
ij = {uij ∈ R4 : Φij(uij) > 0},
R3
ij = {uij ∈ R4 : ft(uij) > 0, t = 3, 4, ft(uij) > 0, t = 2, 9},
R5
ij = {uij ∈ R4 : ft(uij) > 0, t = 3, 4, ft(uij) > 0, t = 5, 10},
R7
ij = {uij ∈ R4 : ft(uij) > 0, t = 6, 8, 9, 11},
R8
ij = {uij ∈ R4 : ft(uij) > 0, t = 9, ft(uij) > 0, t = 6, 7, 12},
R9
ij = {uij ∈ R4 : ft(uij) > 0, t = 5, 7, 10, 12},
R10
ij = {uij ∈ R4 : ft(uij) > 0, t = 10, ft(uij) > 0, t = 5, 8, 11},
R1
ij = intR1
ij , R
q
ij = cl Rq
ij , q = 7, 9,
R
q
ij 6= intR
q
ij , R
q
ij 6= cl Rq
ij , q = 3, 5, 8, 10, в пространстве R4;
3) R4 =
⋃
q=1,4,6,7,8,9,10
R
q
ij , если ai 6= aj и bi = bj , где
R1
ij = {uij ∈ R4 : Φij(uij) > 0},
R4
ij = {uij ∈ R4 : ft(uij) > 0, t = 1, 2, ft(uij) > 0, t = 8, 11},
R6
ij = {uij ∈ R4 : ft(uij) > 0, t = 1, 2, ft(uij) > 0, t = 7, 12},
R7
ij = {uij ∈ R4 : ft(uij) > 0, t = 11, ft(uij) > 0, t = 6, 8, 9},
50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №9
R8
ij = {uij ∈ R4 : ft(uij) > 0, t = 6, 7, 9, 12},
R9
ij = {uij ∈ R4 : ft(uij) > 0, t = 12, ft(uij) > 0, t = 5, 7, 10},
R10
ij = {uij ∈ R4 : ft(uij) > 0, t = 5, 8, 10, 11},
R1
ij = intR1
ij , R
q
ij = cl Rq
ij , q = 8, 10,
R
q
ij 6= intR
q
ij , R
q
ij 6= cl Rq
ij , q = 4, 6, 7, 9, в пространстве R4;
4) R4 =
⋃
q=1,7,8,9,10
R
q
ij , если ai = ajи bi = bj , где
R1
ij = {uij ∈ R4 : Φij(uij) > 0},
R7
ij = {uij ∈ R4 : ft(uij) > 0, t = 11, ft(uij) > 0, t = 6, 8, 9},
R8
ij = {uij ∈ R4 : ft(uij) > 0, t = 9, ft(uij) > 0, t = 6, 7, 12},
R9
ij = {uij ∈ R4 : ft(uij) > 0, t = 12, ft(uij) > 0, t = 5, 7, 10},
R10
ij = {uij ∈ R4 : ft(uij) > 0, t = 10, ft(uij) > 0, t = 5, 8, 11},
R1
ij = intR1
ij ,
R
q
ij 6= intR
q
ij , R
q
ij 6= cl Rq
ij , q = 7, 8, 9, 10, в пространстве R4,
где в 1–4:
Φij(uij) — Φ-функция Pi(ui) и Pj(uj) [4],
f1(uij) = −∆xij + α2
ij , f2(uij) = ∆xij + α2
ij , f3(uij) = −∆yij + β2
ij,
f4(uij) = ∆yij + β2
ij , f5(uij) = −∆xij + α1
ij , f6(uij) = ∆xij + α1
ij ,
f7(uij) = −∆yij + β1
ij , f8(uij) = ∆yij + β1
ij , f9(uij) = −∆xij − α2
ij,
f10(uij) = ∆xij − α2
ij , f11(uij) = −∆yij − β2
ij , f12(uij) = ∆yij − β2
ij ,
∆xij = xj − xi, ∆yij = yj − yi,
ai + aj = α1
ij , |ai − aj | = α2
ij , bi + bj = β1
ij , |bi − bj| = β2
ij .
Теорема 5. Пусть выполняются условия теоремы 4, тогда для семейства прямоу-
гольников Λ(u), u = (u1, . . . , un) ∈ R2n, разбиение пространства R2n имеет вид
R2n =
η⋃
q=1
R2n
q , R2n
q =
n⋂
i>j=1
R
q
ij, (4)
где
η = 10σ1 · 7σ2 · 5σ3 , σ =
3∑
l=1
σl,
σl ∈
{
0, 1, 2, . . . ,
1
2
n(n − 1)
}
, l = 1, 2, 3, σ =
1
2
n(n − 1),
(5)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №9 51
при этом
η = 10σ , если R4 =
11⋃
q=1,q 6=2
R
q
ij или R4 =
10⋃
q=1
R
q
ij , ∀i, j ∈ In, i 6= j,
η = 7σ , если R4 =
⋃
q=1,3,5,7,8,9,10
R
q
ij или R4 =
⋃
q=1,4,6,7,8,9,10
R
q
ij , ∀i, j ∈ In, i 6= j,
η = 5σ , если R4 =
⋃
q=1,7,8,9,10
R
q
ij, ∀i, j ∈ In, i 6= j.
Теорема 6. Пусть выполняются условия теорем 3–5 и Γ-функция [6] для семейства
прямоугольников Λ(u), u = (u1, . . . , un) ∈ R2n, и Ω имеет вид
Γ(u) =
Γ1(u), если u ∈ R2n
1 ,
· · ·
Γq(u), если u ∈ R2n
q ,
· · ·
Γη(u), если u ∈ R2n
η ,
(6)
где Γq(u) = Fq(u, v)|v=0, Fq(u, v)|u=const = Φ(0, v) — Φ-функция H(0) и Ω(v) вида (1). Тогда
справедлива оценка числа локальных максимумов Γ-функции (6)
η∗ 6 µη,
где η определяется соотношением (5),
µ =
K∏
k=1
((0,5mk + 3)4(n−3)(mk + 4)0,25(n−2)2 max{108(mk + 1)3, (0,25mk + 2)8}).
Приведенные результаты могут быть использованы при построении математических мо-
делей двумерных задач покрытия и упаковки в виде задач математического программиро-
вания, что позволяет применить для решения NP-сложных задач этого класса современные
методы локальной и глобальной оптимизации.
1. Daniels K., Inkulu R. An incremental algorithm for translational polygon covering // University of Mas-
sachusetts at Lowell Computer Science Technical Report. – 2001. – No 1. – P. 1–31.
2. Burke E., Heller R., Kendall G., Whitwell G. A new bottom-left-fill heuristic algorithm for the two-
dimensional irregular packing problem // Operations research. – 2006. – 54, No 3. – P. 587–601.
3. Stoyan Yu.G. Φ-function and its basic properties // Доп. НАН України. – 2001. – No 8. – С. 112–117.
4. Stoyan Y., Terno J., Scheithauer G. et al. Φ-function for 2D primary objects // Studia Informatica. –
2002. – 2, No 1. – P. 1–32.
5. Stoyan Y., Scheithauer G., Gil M., Romanova T. Φ-function for complex 2D objects // 4OR Quarterly
J. of the Belgian, French and Italian Operations Research Societies. – 2004. – 2, No 1. – P. 69–84.
6. Stoyan Y. Covering a polygonal region by a collection of various size rectangles // Пробл. машинострое-
ния. – 2007. – 10, No 2. – С. 67–82.
Поступило в редакцию 19.03.2008Институт проблем машиностроения
им. А.Н. Подгорного НАН Украины, Харьков
52 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №9
|
| id | nasplib_isofts_kiev_ua-123456789-5824 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T18:04:41Z |
| publishDate | 2008 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Романова, Т.Е. Кривуля, А.В. 2010-02-08T15:07:54Z 2010-02-08T15:07:54Z 2008 Средства математического моделирования задач покрытия / Т.Е. Романова, А.В. Кривуля // Доп. НАН України. — 2008. — № 9. — С. 48-52. — Бібліогр.: 6 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/5824 519.85 The article considers theorems which are useful for the mathematical and computer modeling of the covering problems of a compact canonical multiconnected polygonal set with a finite family of convex polygons. Based on peculiarities of a rectangular cover, theorems concerning a partition of the translation vector space and an upper bound of the number of local extrema of the Г-function are formulated. ru Видавничий дім "Академперіодика" НАН України Інформатика та кібернетика Средства математического моделирования задач покрытия Article published earlier |
| spellingShingle | Средства математического моделирования задач покрытия Романова, Т.Е. Кривуля, А.В. Інформатика та кібернетика |
| title | Средства математического моделирования задач покрытия |
| title_full | Средства математического моделирования задач покрытия |
| title_fullStr | Средства математического моделирования задач покрытия |
| title_full_unstemmed | Средства математического моделирования задач покрытия |
| title_short | Средства математического моделирования задач покрытия |
| title_sort | средства математического моделирования задач покрытия |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/5824 |
| work_keys_str_mv | AT romanovate sredstvamatematičeskogomodelirovaniâzadačpokrytiâ AT krivulâav sredstvamatematičeskogomodelirovaniâzadačpokrytiâ |