Покрытие компактной многогранной области конечным семейством прямых параллелепипедов
Розглядається задача покриття компактної багатогранної області з непустою внутрішністю скінченною кількістю прямих паралелепіпедів. На базі техніки Γ-функцій побудована математична модель задачі та досліджені її основні властивості. На основі цих властивостей запропоновано стратегію розв'язку з...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/30008 |
| 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: | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов / Ю. Г. Стоян, Е.С. Сосюрка // Доп. НАН України. — 2010. — № 8. — С. 43-48. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859900880654958592 |
|---|---|
| author | Стоян, Ю.Г. Сосюрка, Е.С. |
| author_facet | Стоян, Ю.Г. Сосюрка, Е.С. |
| citation_txt | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов / Ю. Г. Стоян, Е.С. Сосюрка // Доп. НАН України. — 2010. — № 8. — С. 43-48. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Розглядається задача покриття компактної багатогранної області з непустою внутрішністю скінченною кількістю прямих паралелепіпедів. На базі техніки Γ-функцій побудована математична модель задачі та досліджені її основні властивості. На основі цих властивостей запропоновано стратегію розв'язку задачі. Наведено результати чисельних експериментів.
The covering problem of a non-convex polytope with non-empty interior by a finite number of parallelepipeds is discussed. On the ground of the Γ-function technique, a mathematical model of the problem is constructed, and its basic characteristics are analyzed. On the basis of these characteristics, the solution strategy is offered. Numerical examples are given.
|
| first_indexed | 2025-12-07T15:57:39Z |
| format | Article |
| fulltext |
УДК 519.853.7
© 2010
Член-корреспондент НАН Украины Ю.Г. Стоян, Е. С. Сосюрка
Покрытие компактной многогранной области конечным
семейством прямых параллелепипедов
Розглядається задача покриття компактної багатогранної областi з непустою внут-
рiшнiстю скiнченною кiлькiстю прямих паралелепiпедiв. На базi технiки Γ-функцiй по-
будована математична модель задачi та дослiдженi її основнi властивостi. На основi
цих властивостей запропоновано стратегiю розв’язку задачi. Наведено результати чи-
сельних експериментiв.
Пусть задано конечное семейство параллелепипедов
Λ={Pi = {(x, y, z) ∈ R
3 : − ai 6 x 6 ai,−bi 6 y 6 bi,−ci 6 z 6 ci}, i ∈ I={1, 2, . . . , n}},
где R
3 — трехмерное арифметическое евклидово пространство, и многогранное множество
Ω ⊂ R
3 такое, что Ω =
m⋃
j=1
Ωj,
Ωj = {(x, y, z) ∈ R
3 : Ajkx+Bjky + Cjkz +Djk 6 0, k ∈ I̟ = {1, 2, . . . ,̟j}},
int(Ωj) 6= ∅, j ∈ J = {1, 2, . . . ,m}, int(·) — внутренность множества (·) [1]. Полагаем,
что местоположение Ω в R
3 фиксировано. Параллелепипед Pi, транслированный на вектор
ui = (xi, yi, zi), обозначим Pi(ui), а семейство транслированных параллелепипедов — через
Λ(u), где u = (u1, u2, . . . , un) ∈ R
3n.
Определение [2]. Семейство Λ(u) называется покрытием области Ω, если существует
вектор u0 ∈ R
3n, такой, что
Ω
⋂
(
n⋃
i=1
Pi(u
0
i )
)
= Ω. (1)
Задача. Необходимо определить, существует ли вектор u ∈ R
3n такой, что выполня-
ется (1).
Пусть u0 ∈ R
3n — некоторый фиксированный вектор. Тогда множество P (u0) =
=
n⋃
i=1
Pi(u
0
i ) ⊂ R
3. Построим H(u0) = R
3 \ intP (u0). На основании двойственности тео-
ретико-множественных операций [3]: H(u0) = R
3 \
n⋃
i=1
intPi(u
0
i ) =
n⋂
i=1
(R3 \ intPi(u
0
i )). Тогда
условие (1) может быть записано в эквивалентном виде:
Ω
⋂
H(u0) = ∅. (2)
Рассмотрим параллелепипеды Pi(ui) и Pj(uj). Пусть параллелепипеду Pk(uk), k = i, j
соответствует набор вершин {vkp , p = 1, 2, . . . , 8}, набор ребер {ekp, p = 1, 2, . . . , 12}, набор
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №8 43
Рис. 1
граней {fk
p , p = 1, 2, . . . , 6}. Тогда взаимное размещение параллелепипедов Pi(ui) и Pj(uj)
может быть одним из видов, представленных на рис. 1.
Возможны следующие типы взаимного размещения Pi(ui) и Pj(uj):
1) Pi(ui)
⋂
Pj(uj) = ∅ (рис. 1, а);
2) существует vjp ∈ Pi(ui) и vih ∈ Pj(uj), и для любого g верно, что ejg 6⊂ Pi(ui) (в зави-
симости от номеров вершин, возможно восемь типов) (рис. 1, б );
3) существует ejp ⊂ Pi(ui) и для любого h верно, чтоf j
h 6⊂ Pi(ui) (в зависимости от номера
ребра, возможно двенадцать типов) (рис. 1, в);
4) существуетf j
p ⊂ Pi(ui) и Pj(uj) 6⊂ Pi(ui) (в зависимости от номера грани, возможно
шесть типов) (рис. 1, г);
5) для любых h, p, g верно, что vjh, ejp, f j
g /∈ Pi(ui), а intPi(ui)
⋂
intPj(uj) 6= ∅ или
Pj(uj) ⊂ Pi(ui) (возможно четыре типа) (рис. 1, д).
Таким образом, существует не более чем 31 тип взаимного расположения параллелепи-
педов Pi(ui) и Pj(uj). Тогда
Hij(ui, uj) = (R3 \ intPi(ui))
⋃
(R3 \ intPj(uj))
можно представить в виде объединения подсемейств Hk
ij(ui, uj), k ∈ L = {1, 2, . . . , 31} [4],
каждое из которых состоит из множеств одного типа. Это значит, пространство параметров
размещения параллелепипедов Pi и Pj можно разбить на такие подмножества Rk
ij , что если
44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №8
(ui, uj) ∈ Rk
ij, то множество h(ui, uj) ∈ Hk
ij . Следовательно, R6 =
31⋃
k=1
Rk
ij , где каждому
множеству Rk
ij соответствует Hk
ij, k ∈ L.
Определение [2, 4]. Если h(u1i , u
1
j ), h(u
2
i , u
2
j ) ∈ Hk
ij(ui, uj), то говорим, что h(u1i , u
1
j )
и h(u2i , u
2
j ) имеют пространственную форму k-го типа.
Пусть теперь H(u) =
n⋃
i=1
(R3 \ intPi(ui)), u ∈ R
3n. По аналогии со случаем двух па-
раллелепипедов, рассматриваем взаимное расположение каждой пары параллелепипедов
семейства Λ(u), т. е. каждому множеству h ∈ H(u) может быть поставлена во взаимноодно-
значное соответствие следующая матрица:
Mq =
mk1
12 mk2
13 . . . m
kn−1
1n
0 mkn
23 . . . m
k2n−2
2n
. . . . . . . . . . . .
0 0 . . . m
kn(n−1)/2
n−1,n
,
где mkt
ij ∈ {Rkt
ij , kt ∈ L}, t = 1, 2, . . . , n(n − 1)/2, q = 1, 2, . . . , 31, если, k2 = k3 = · · · =
= kn(n−1)/2 ∈ L; q = 1, 2, . . . , 312, если k1, k2 ∈ L, k3 = · · · = kn(n−1)/2 ∈ L; . . . ; q =
= 1, 2, . . . , 31n(n−1)/2, если k1, k2, . . . , kn(n−1)/2 ∈ L.
Определение [2, 4]. Множества h(u1) и h(u2) имеют одинаковую пространственную
форму, если они определяются одинаковыми матрицами Mq.
Теорема 1 [4, 5]. Для семейства прямых параллелепипедов Λ(u) разбиение пространс-
тва R
3n имеет вид:
R
3n =
η⋃
q=1
R3n
q , R3n
q =
n⋃
j>i=1
n(n−1)/2⋃
t=1
Skt
ij , (3)
где η = 28σ1 · 19σ2 · 13σ3 · 9σ4 , σl ∈ {0, 1, 2, . . . , n(n − 1)/2}, l = 1, 2, 3, 4,
4∑
l=1
σl = n(n − 1)/2,
Skt
ij — прямая призма с основанием Rkt
ij .
В [6] показано, что h(u) ∈ H(u) представимо в виде конечного объединения базовых мно-
жеств, а именно: полупространств C0
δ , δ = 1, 2, . . . , 6, двугранных углов C2
δ , δ = 7, 8, . . . , 18,
трехгранных углов C3
δ , δ = 19, 20, . . . , 26, полубесконечных цилиндров с прямоугольным
основанием C4
δ , δ = 27, 28, . . . , 32, цилиндров с прямоугольным основанием C5
δ , δ = 32, 33, 34
и прямых параллелепипедов C1. То есть, h(u) =
λ⋃
j=1
Cj(wij), где
Cj ∈ C̃ = {C0
δ , C
2
δ , C
3
δ , C
4
δ , C
5
δ , C
1, δ = 1, 2, . . . , 35},
wij состоит из не более чем 6 соответствующих компонент вектора u.
Заметим, если u ∈ R3n
q ⊂ R
3n, то Hq(u), q ∈ Q = {1, 2, . . . , η} состоят из множеств одной
и той же пространственной формы и отличаются только метрическими характеристиками.
В терминах Φ-функции [7, 8] соотношение (2) может быть описано неравенством:
Φ(u0, v) > 0, (4)
где Φ(u0, v) — Ф-функция множеств H(u0) и Ω(v) [9, 10], v = (xv , yv, zv).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №8 45
Поскольку Φ-функция для h(u0) ∈ H3n
q (u) и Ω имеет вид: Φq(u
0, v) = min{Φqj(u
0, v), j ∈
∈ Iλ}, где Φqj — Φ-функция множеств Cj и Ω, то Φ-функции для любого u ∈ intR3n
q имеют
один и тот же вид [2, 8] и отличаются только значениями коэффициентов. Следовательно,
взяв u ∈ intR3n
q в качестве переменной в Φq, получим следующую функцию: Fq(u, v) =
= min{Fqj(u, v), j ∈ Iλ}, Fq(u, v)
∣∣
u=u0 = Φq(u
0, v). Легко видеть, что если Fq(u
∗, v∗) > 0, то
Ω
⋃
h(u∗) = ∅. Принимая во внимание (3), положив v = 0, построим Γ-функцию (функцию
покрытия) [2, 9]: для множеств Ω и H(u)
Γ(u) =
Γ1(u), u ∈ R3n
1 ,
Γ2(u), u ∈ R3n
2 ,
. . .
Γη(u), u ∈ R3n
η .
(5)
Таким образом, если найдется вектор u∗ ∈ R
3n такой, что Γ(u∗) > 0, то Ω
⋃
intH(u∗) =
= ∅.
Теорема 2 [6, 10]. Γ(u) — кусочно-линейная функция, претерпевающая разрыв I рода
при u ∈
31⋃
q=2
n⋃
i>j=1
(
frR1
ij
⋃
frRq
ij
)
.
Оценка числа функций, описывающих Γ(u), имеет вид:
θ =
η∑
q=1
ϕqNq,
где
ϕq =
12∑
δ=1
µq2δ +
8∑
δ=1
µq3δ +
6∑
δ=1
µq4δ +
3∑
δ=1
µq5δ + µq1,
Nq 6 N = ϑµ91
1
12∏
δ=1
ϑ
µq2δ
2δ
8∏
δ=1
ϑ
µq3δ
3δ
6∏
δ=1
ϑ
µq4δ
4δ
3∏
δ=1
ϑµq5δ
5δ ,
µq2δ, µq3δ, µq4δ, µq5δ, µq1 — число базовых множеств C0
δ , C2
δ , C3
δ , C4
δ , C5
δ , C1, участвующих
в формировании множества H(u0) [6], ϑjδ — число функций, участвующих в формировании
Φ-функций для Cj
δ и Ω, j = 1, 2, 3, 4, 5.
Как следует из построения функции Γ(u), решение поставленной задачи может быть
сведено к
Γ(u∗) = max
u∈R3n
Γ(u). (6)
Тогда, если Γ(u∗) < 0, то (2) не выполняется, если Γ(u∗) > 0, то (2) выполнено и u∗ —
искомый вектор параметров размещения.
Решение задачи (6) сводится к решению последовательности задач линейного програм-
мирования: max
q∈Q
Γq(u
∗), где Γq(u
∗) = max
u∈R3n
q
Γq(u).
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №8
Таблица 1
v1t 1 2 3 4 5 6
x1t −120 −110 −80 −10 −80 −80
y1t 0 100 120 −110 0 0
z1t 0 0 0 0 −40 40
v2t 1 2 3 4 5 6
x1t −110 −60 120 −40 −20 —
y1t 30 120 100 90 90 —
z1t 0 0 0 50 −40 —
v3t 1 2 3 4 5 6
x1t 100 60 140 110 110 —
y1t −100 120 40 30 −20 —
z1t 0 0 0 −50 50 —
v4t 1 2 3 4 5 6
x1t −50 30 120 40 40 —
y1t −100 −50 −70 −70 −70 —
z1t 0 0 0 −40 40 —
Таблица 2
Размер
параллелепипида P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
a 50 40 60 50 60 50 40 30 30 50
b 50 40 40 50 50 50 40 40 50 50
c 60 50 50 30 60 50 60 60 50 40
Для решения задачи max
u∈R3n
q
Γq(u) строится дерево решений. Каждой p-й концевой вер-
шине этого дерева соответствует функция Γqp(u), u ∈ R3n
q , p ∈ {1, 2, . . . ,Nq}.
Поскольку задача (6) является многоэкстремальной, NP-полной и NP-трудной [11], то,
в общем случае, в настоящее время глобального максимума можно достичь только теоре-
тически.
Для поиска приближения к глобальному максимуму используется стратегия, изложен-
ная в [12, 13].
П р и м е р . Пусть задана двухсвязная многогранная область Ω, представленная объединением
выпуклых многогранников Ωj , j = 1, 2, 3, 4. Полагаем, что Ωj задается последовательностью вер-
шин vjt, t = 1, 2, . . . , ̟j, координаты которых приведены в табл. 1.
Информация о метрических характеристиках параллелепипедов Pi, i = 1, 2, . . . , 10, при-
ведена в табл. 2.
Вектор u0 = ((59, 100, 91), (43, 43, 86), (81, 69, 67), (45, 95, 69), (33, 99, 73), (94, 37, 95), (38,
90, 75), (17, 85, 45), (40, 24, 32), (81, 35, 48)) соответствует начальному размещению паралле-
лепипедов Pi, i = 1, 2, . . . , 10.
Искомый вектор параметров размещения, удовлетворяющий условию покрытия (2) —
u∗ = ((−83, 88, 0), (−70, 91, 2), (75, 107, 0), (112, 30, 20), (−72, 20, 17), (−67,−71,−3), (0,−83,
−10), (60,−72, 0), (111,−59, 2), (109, 30,−15)).
1. Александрян Г.А., Мирзаханян Э.А. Общая топология. – Москва: Высш. шк., 1979. – 336 с.
2. Stoyan Yu. Covering a polygonal region by a collection of various size rectangles // Пробл. машинострое-
ния. – 2007. – 10, No 2. – С. 67–82.
3. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа: – Москва:
Наука, 1981. – 544 с.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2010, №8 47
4. Сосюрка Е. С. Аналитическое описание взаимного расположения прямых параллелепипедов в задаче
покрытия компактного многогранного множества // Вестн. Харьк. нац. ун-та. – 2008. – № 833. –
С. 247–257.
5. Романова Т. Е., Кривуля А.В. Средства математического моделирования задач покрытия // Доп.
НАН України. – 2008. – № 9. – С. 48–52.
6. Сосюрка Е. С. Построение гамма-функции и ее использование для решения задачи покрытия ком-
пактного многогранного множества семейством прямых параллелепипедов // Вестн. Харьк. нац.
ун-та. – 2009. – № 847. – С. 314–323.
7. Stoyan Yu., Scheithauer G., Pridatko D., Romanova T. Φ-function for primary 3D objects // Technische
Universitat Dresden. – 2002. – P. 27.
8. Стоян Ю.Г., Придатко Д.И., Романова Т. Е., Шайтхауэр Г. Φ-функции объектов, имеющих про-
странственную форму границы, – конус, цилиндр, параллелепипед // Доп. НАН України. – 2004. –
№ 5. – С. 28–33.
9. Stoyan Yu., Scheithauer G., Gil N., Romanova T. Φ-function for complex 2D objects // 4QR Quarterly
J. of the Belgian, French and Italian Operations Research Societies. – 2004. – 2, No 1. – P. 69–84.
10. Stoyan Yu.G. Φ-function and its basic properties // Доп. НАН України. – 2001. – No 8. – С. 112–117.
11. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – Москва:
Мир, 1985. – 512 с.
12. Романова Т. Е., Кривуля А.В., Злотник М.В. Трансляционное прямоугольное покрытие // Доп.
НАН України. – 2008. – № 7. – С. 48–53.
13. Романова Т. Е., Кривуля А.В., Злотник М.В. Математическая модель и метод решения задачи по-
крытия многоугольной области прямоугольными объектами // Пробл. машиностроения. – 2008. – 11,
№ 3. – С. 58–67.
Поступило в редакцию 22.02.2010Институт проблем машиностроения
им. А.Н. Подгорного НАН Украины, Харьков
Corresponding Member of the NAS of Ukraine Yu.G. Stoyan, O. S. Sosuyrka
The covering of a non-convex polytope by a finite family of right
parallelepipeds
The covering problem of a non-convex polytope with non-empty interior by a finite number of
parallelepipeds is discussed. On the ground of the Γ-function technique, a mathematical model
of the problem is constructed, and its basic characteristics are analyzed. On the basis of these
characteristics, the solution strategy is offered. Numerical examples are given.
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2010, №8
|
| id | nasplib_isofts_kiev_ua-123456789-30008 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T15:57:39Z |
| publishDate | 2010 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Стоян, Ю.Г. Сосюрка, Е.С. 2012-01-17T10:57:36Z 2012-01-17T10:57:36Z 2010 Покрытие компактной многогранной области конечным семейством прямых параллелепипедов / Ю. Г. Стоян, Е.С. Сосюрка // Доп. НАН України. — 2010. — № 8. — С. 43-48. — Бібліогр.: 13 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/30008 519.853.7 Розглядається задача покриття компактної багатогранної області з непустою внутрішністю скінченною кількістю прямих паралелепіпедів. На базі техніки Γ-функцій побудована математична модель задачі та досліджені її основні властивості. На основі цих властивостей запропоновано стратегію розв'язку задачі. Наведено результати чисельних експериментів. The covering problem of a non-convex polytope with non-empty interior by a finite number of parallelepipeds is discussed. On the ground of the Γ-function technique, a mathematical model of the problem is constructed, and its basic characteristics are analyzed. On the basis of these characteristics, the solution strategy is offered. Numerical examples are given. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Покрытие компактной многогранной области конечным семейством прямых параллелепипедов The covering of a non-convex polytope by a finite family of right parallelepipeds Article published earlier |
| spellingShingle | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов Стоян, Ю.Г. Сосюрка, Е.С. Інформатика та кібернетика |
| title | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов |
| title_alt | The covering of a non-convex polytope by a finite family of right parallelepipeds |
| title_full | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов |
| title_fullStr | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов |
| title_full_unstemmed | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов |
| title_short | Покрытие компактной многогранной области конечным семейством прямых параллелепипедов |
| title_sort | покрытие компактной многогранной области конечным семейством прямых параллелепипедов |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/30008 |
| work_keys_str_mv | AT stoânûg pokrytiekompaktnoimnogogrannoioblastikonečnymsemeistvomprâmyhparallelepipedov AT sosûrkaes pokrytiekompaktnoimnogogrannoioblastikonečnymsemeistvomprâmyhparallelepipedov AT stoânûg thecoveringofanonconvexpolytopebyafinitefamilyofrightparallelepipeds AT sosûrkaes thecoveringofanonconvexpolytopebyafinitefamilyofrightparallelepipeds |