Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров
Задача зводиться до низки задач мiнiмiзацiї радiуса куль при фiксованiй їх кiлькостi. Функцiя мети являє собою мiнiмум скiнченної кiлькостi опуклих гладких функцiй. Показано, що екстремуми досягаються у вершинах багатогранникiв Вороного, побудованих для центрiв куль. Для знаходження екстремумiв заст...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/8507 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров / Ю. Г. Стоян, В.Н. Пацук // Доп. НАН України. — 2009. — № 5. — С. 41-45. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859737498066878464 |
|---|---|
| author | Стоян, Ю.Г. Пацук, В.Н. |
| author_facet | Стоян, Ю.Г. Пацук, В.Н. |
| citation_txt | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров / Ю. Г. Стоян, В.Н. Пацук // Доп. НАН України. — 2009. — № 5. — С. 41-45. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| description | Задача зводиться до низки задач мiнiмiзацiї радiуса куль при фiксованiй їх кiлькостi. Функцiя мети являє собою мiнiмум скiнченної кiлькостi опуклих гладких функцiй. Показано, що екстремуми досягаються у вершинах багатогранникiв Вороного, побудованих для центрiв куль. Для знаходження екстремумiв застосовується метод можливих напрямкiв у комбiнацiї з випадковим пошуком. Наведено низку чисельних прикладiв.
The problem is reduced to a sequence of sphere radius minimization problems when fixing the number of spheres. The objective function is the minimum of a finite number of convex smooth functions. It is shown that the extrema are reached at the vertices of the Voronoi polyhedra constructed for the centers of the spheres. The method of feasible directions in combination with a random search is applied for searching the extrema. A number of numerical examples is given.
|
| first_indexed | 2025-12-01T15:15:59Z |
| format | Article |
| fulltext |
УДК 517
© 2009
Член-корреспондент НАН Украины Ю.Г. Стоян, В. Н. Пацук
Метод покрытия выпуклого многогранного множества
минимальным количеством одинаковых шаров
Задача зводиться до низки задач мiнiмiзацiї радiуса куль при фiксованiй їх кiлькостi.
Функцiя мети являє собою мiнiмум скiнченної кiлькостi опуклих гладких функцiй. По-
казано, що екстремуми досягаються у вершинах багатогранникiв Вороного, побудованих
для центрiв куль. Для знаходження екстремумiв застосовується метод можливих на-
прямкiв у комбiнацiї з випадковим пошуком. Наведено низку чисельних прикладiв.
Пусть имеется компактное многогранное множество P ⊂ R
3, где R
3 — арифметическое
евклидово трeхмерное пространство, и конгруэнтные шары Si радиуса r с координатами
центров ui = (xi, yi, zi), i = 1, 2, . . . , n.
Шар Si, транслированный на вектор ui, обозначается Si(ui).
Определение 1. Шары Si, i = 1, 2, . . . , k, покрывают множество P , если
P
⋂
(
k
⋃
i=1
Si(ui)
)
= P. (1)
Задача 1. Требуется покрыть множество P минимальным количеством шаров Si, i =
= 1, 2, . . . , k 6 n.
Решение задачи может быть сведено к решению последовательности k + 1 следующих
задач.
Задача 2. Требуется покрыть множество P шарами Si, i = 1, 2, . . . , k, минимального
радиуса r.
Таким образом, если в результате решения задачи 2 выполняется условие (1),
а P
⋂
(
k+1
⋃
i=1
Si(ui)
)
6= P , то решение задачи (1) равно k.
Предлагаемая математическая модель задачи 2 является развитием результатов [1] для
трехмерного случая.
Пусть шары задаются неравенствами
ϕi(x, y, z, ui) = ϕi(v, ui) = (x − xi)
2 + (y − yi)
2 + (z − zi)
2 − r2
6 0,
i = 1, 2, . . . , k.
(2)
Построим функцию
Φ(v, u) = min{ϕ1(v, u1), ϕ2(v, u2), . . . , ϕk(v, uk)}, (3)
где u = (u1, u2, . . . , uk) ∈ R
3k, и рассмотрим некоторые ее свойства.
1. Как известно [2–4], функция (3) всюду определена и непрерывна.
2. Поскольку каждая функция ϕi(v, ui), i = 1, 2, . . . , k, не ограничена сверху, ограничена
снизу и min ϕi(v, ui) = −r2 при (v, ui) ∈ R
6, i = 1, 2, . . . , k, то функция Φ(v, u) не ограничена
сверху, ограничена снизу и min Φ(x, y, u) = −r2 при (v, u) ∈ R
m, где m = 3k + 3.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №5 41
3. Для любого фиксированного v = v∗ ∈ R
3 функция Γ(u) = Φ(v∗, u) кусочно-гладкая.
4. Теорема 1. Для любого фиксированного u = u∗ = (u∗
1, u
∗
2, . . . , u
∗
n) функция F (v) =
= Φ(v, u∗) имеет конечное число локальных максимумов и их число не больше числа вер-
шин многогранников Вороного [5, 6], построенных для точек Oi(u
∗
i ) ∈ R
3, i = 1, 2, . . . , k.
5. Пусть Vi, i = 1, 2, . . . , k, — многогранники Вороного [6] для точек Oi(u
∗
i ), i = 1, 2, . . . , k.
Не уменьшая общности, полагаем, что многогранники Vi, i = 1, 2, . . . , t, ограничены, мно-
гогранники Vi, i = t + 1, t + 2, . . . , k, не ограничены.
Назовем Vj
⋂
P , i = 1, 2, . . . , k, многогранниками Вороного в P .
Теорема 2. На множестве P функция F (v) имеет не более l = l(v) = l1 + l2 + l3 +
+ l4 локальных минимумов, где L1 — множество вершин многогранников Вороного, L2 —
множество точек пересечения ребер многогранников Vj , j = t + 1, t + 2, . . . , k, и граней
множества P , L3 — множество точек пересечения граней многогранников Vj, j = t + 1,
t + 2, . . . , k, и ребер множества P , L4 — множество вершин множества P , lµ = cardLµ,
µ = 1, 2, 3, 4.
6. max
v∈P
F (v) = max
v∈L
F (v).
7. Каждая точка (v∗, γ∗) ∈ R
4, где v∗ ∈ L1, γ∗ = F (v∗), является одним из решений
системы
(x − x∗
i1
)2 + (y − y∗i1)
2 + (z − z∗i1)
2 − r2 − γ = 0,
(x − x∗
i2
)2 + (y − y∗i2)
2 + (z − z∗i2)
2 − r2 − γ = 0,
(x − x∗
i3
)2 + (y − y∗i3)
2 + (z − z∗i3)
2 − r2 − γ = 0,
(x − x∗
i4
)2 + (y − y∗i4)
2 + (z − z∗i4)
2 − r2 − γ = 0
(4)
относительно x, y, z и γ.
8. Теорема 3. Если точка v∗ ∈ intH(u∗
i1
, u∗
i2
, u∗
i3
, u∗
i4
), v∗ ∈ L1, где H(u∗
i1
, u∗
i2
, u∗
i3
, u∗
i4
) —
выпуклая оболочка точек u∗
i1
, u∗
i2
, u∗
i3
, u∗
i4
∈ R
3, то в точке v∗ достигается локальный
максимум функции F (v). Если точка v∗ /∈ intH(u∗
i1
, u∗
i2
, u∗
i3
, u∗
i4
), то в точке v∗ локальный
максимум функции F (v) не достигается.
9. Если max F (v) = α > 0 при условии v ∈ L, то шары Si, i = 1, 2, . . . , k, не покрывают
множество P , и чем больше α, тем меньше покрытая часть множества P .
10. Если maxF (v) 6 0 при условии v ∈ L, то шары Si, i = 1, 2, . . . , k, покрывают
множество P .
Свойства функции Φ(v, u) позволяют представить математическую модель задачи (2)
в виде
min
u∈G
max
v∈P
Φ(v, u) = α∗, (5)
где G = G1 × G2 × · · · × Gk, G1 = G2 = · · · = Gk = W , W = P ⊕ Sε, ⊕ — знак операции
суммы Минковского [7], Sε — шар радиуса r − ε, ε > 0.
Свойства математической модели.
(i) Значение α∗ достигается по меньшей мере в k! различных точках. Действительно,
пусть min
u∈G
max
v∈P
Φ(v, u) = Φ(v∗, u∗) = α∗ и u∗
i 6= u∗
j для i 6= j. Используя точку u∗ =
= (u∗
1, u
∗
2, . . . , u
∗
k), можно построить точку u∗1 = (u∗1
1 , u∗1
2 , . . . , u∗1
k ), где u∗1
1 = u∗
2, u∗1
2 = u∗
1,
u∗1
2+i = u∗
2+i, i = 3, 4, . . . , k. Поскольку радиусы шаров Si, i = 1, 2, . . . , k, одинаковы, то
Φ(v∗, u∗) = Φ(v∗, u∗1) = α∗. Различных точек такого вида k!. Т. е. перестановка компонент
вектора u∗ дает новый вектор с тем же значением функции цели.
42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №5
(ii) Одинаковое значение α∗ может достигаться в разных точках v ∈ P .
П р и м е р 1 . Пусть P — параллелепипед P = {v ∈ R
3, 0 6 x 6 2r, 0 6 y 6 2r, 0 6 z 6 4r} и u =
= (u1, u2), u∗1
1
= (r, r, r), u∗1
2
= (r, r, 3r). Легко видеть, что min
u∈G
max
v∈P
Φ(v, u) = Φ(v∗, u∗) = α∗1 = 3r2.
При этом значение α∗1 достигается во всех вершинах параллелепипеда R.
(iii) Задача 2 может иметь несколько различных точек локального минимакса (v∗i, u∗i),
i = 1, 2, . . . , ν, таких, что α∗i 6= α∗j для i 6= j, где α∗i = Φ(v∗i, u∗i). В общем случае может
существовать непрерывное семейство локальных минималей.
(iv) Допустимая область G такова, что любой вектор u ∈ G гарантирует участие всех
шаров Si, i = 1, 2, . . . , k, в покрытии множества P .
Для решения задачи 1 прежде всего необходимо решить задачу 2 для некоторого k.
В результате решения найдется вектор u = u∗. Если max
v
Φ(v, u∗) 6 0, решение найдено,
иначе увеличиваем k (или делаем еще одну попытку).
Свойства задачи 2, включая свойства функции Φ(v, u), приводят к следующей стратегии
решения.
Ш а г 1 . Полагаем s = 0. Значения вектора u = us = (us
1, u
s
2, . . . , u
s
k) ∈ G генерируются
случайным или иным образом так, что us
i 6= us
j для i 6= j.
Ш а г 2 . Для точек us
i ∈ W ⊂ R
3, i = 1, 2, . . . , k, строим многогранники Вороного
в пространстве R
3 и формируем множество Ls = L(us).
Ш а г 3 . Вычисляем rs = max
v∈L
F (v). Если rs = 0, то задача решена.
Ш а г 4 . В противном случае пусть Qs — множество пар (l, i) таких, что vs
l — одна из
вершин многогранника Вороного в области P , построенного для точки Os
i = O(us
i ) и
max
v∈P
Φ(v, us) − ϕ(vs
l , u
s) = δli 6 δ, l ∈ Ls, (6)
где δ выбирается из соображений увеличения скорости сходимости. Можно представить
Qs = Qs
1
⋃
Qs
2
⋃
Qs
3
⋃
Qs
4, где
Qs
τ = {q = (l, i) ∈ Qs | l ∈ Ls
τ , τ = 1, 2, 3, 4}. (7)
Пусть грани области P задаются уравнениями
χλ(x, y, z) = aλx + bλy + cλz + dλ = 0, λ = 1, 2, . . . ,Λ. (8)
Пусть V s = vs
1, v
s
2, . . . , v
s
T s = {vs
l ∈ Ls такое, что существует i такое, что (l, i) ∈ Qs} и M s
µ —
проекции Qs
µ на Ls, µ = 1, 2, 3, 4, т. е. l ∈ M s
µ, если (l, i) ∈ Qs и l ∈ Ls
µ. Полагаем
M = M1
⋃
M2
⋃
M3
⋃
M4.
Пусть Js = {j ∈ {1, 2, . . . , k} такое, что существует (t, j) ∈ Q}. Перенумеруем vs
t для про-
стоты, начиная с индексов из Ls
1, затем Ls
2 и т. д. Введем функцию Ψ(v1, v2, . . . , vq, u) =
= max
(j,i)∈J
ϕi(vj , ui) при условии, что ui удовлетворяют соответствующим условиям (8): одному
при ui ∈ L2, двум при ui ∈ L3. vi = const при vi ∈ L4, поэтому ϕi(vj , ui) = ϕ⋆
i (vj). Положим,
что v1, v2, . . . , vT s — независимые переменные. Тогда по построению многоугольников Во-
роного в невырожденном случае (т. е. когда вершине многогранника Вороного инцидентны
четыре других вершины и расстояние до инцидентных вершин превышает вычислительную
погрешность) в некоторой окрестности точки u = us имеем min
(v1,v2,...,vq)∈Rq
Ψ(v1, v2, . . . , vq, u) =
= max
v∈P
Φ(v, u).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №5 43
Рис. 1. Покрытие куба 10 шарами
Таким образом, нахождение локального минимума задачи 2 можно свести к последова-
тельному поиску min
(v1,v2,...,vq,u)∈Rq+k
Ψ(v1, v2, . . . , vq, u). Для решения этой задачи применяется
модификация метода возможных направлений [8].
Ш а г 5 . Находим Qs = Q(us) из (6), (7).
Ш а г 6 . Пусть ζ = (ξ, η) = (ξ1, ξ2, . . . , ξT s , ηT s+1, ηT s+2, . . . , ηT s+cardJs) — вектор возмо-
жных направлений; χp1(t)(v
s
t ) = 0 — уравнение, определяющее грань P , на которой лежит vs
t
в случае t ∈ Ls
2, χp1(t)(v
s
t ) = 0, χp2(t)(v
s
t ) = 0 — уравнения, определяющие ребро области P ,
на которой лежит vs
t в случае t ∈ Ls
3.
Решаем задачу линейного программирования
min
κ∈R1
κ (9)
при условии
(∇ϕtj(v
s
t , u
s
j), ζ) 6 κ, (t, j) ∈ Qs
1
⋃
Qs
2
⋃
Qs
3,
(∇ϕ⋆
t (u
s
j), η) 6 κ, (t, j) ∈ Qs
4,
χp1(t)(v
s
t + ξt) = 0, t ∈ M s
2
⋃
M s
3 ,
χp2(t)(v
s
t + ξt) = 0, t ∈ M s
3 ,
−1 6 ζi 6 1, i = 1, 2, . . . , card(M s) + card(Js).
(10)
Таблица 1
Количество шаров Радиус
1 0,866039764304762
2 0,750002614895996
3 0,709865727467255
4 0,612372997325949
5 0,590845025200821
6 0,563243394708008
7 0,544744800066187
8 0,433035862747464
9 0,417171214922348
10 0,409395789425591
44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2009, №5
Если в результате решения задачи получаем κ 6 0, то точка u стационарна, т. е. это
может быть точка локального минимума, нестрогого локального минимума или седловая
точка.
П р и м е р 2 . Имеется множество одинаковых Si, i = 1, 2, . . . , n, и куб P = {v ∈ R
3, 0 6 x 6 1,
0 6 y 6 1, 0 6 z 6 1}. Необходимо определить минимальный радиус r k покрывающих шаров Si
и вектора u = (u1, u2, . . . , uk) ∈ R
3k, обеспечивающие покрытие множества P , k = 1, 2, . . . , 10. Ре-
зультаты расчета локально оптимального покрытия для 10 шаров приведены на рис. 1. Зависимость
радиуса шара наилучшего из полученных локально оптимальных покрытий от количества шаров
приведены в табл. 1.
1. Стоян Ю.Г., Пацук В.Н. Покрытие многоугольной области минимальным количеством одинаковых
кругов заданного радиуса // Доп. НАН України. – 2006. – № 3. – С. 74–77.
2. Рвачев В.Л. Геометрические приложения алгебры логики. – Киев: Технiка, 1967. – 212 с.
3. Рвачев В.Л. Методы алгебры логики в математической физике. – Киев: Наук. думка, 1974. – 259 с.
4. Рвачев В.Л. Теория R-функций и некоторые ее приложения. – Киев: Наук. думка, 1982. – 552 с.
5. Voronoi G. F. Recherches sur les paralléloèdres primitifs // J. reine und angew. Math. – 1908. – 134. –
С. 198–287.
6. Вороной Г.Ф. Собрание сочинений. – Киев: Изд-во АН УССР, 1952. – Т. 2. – С. 171–368.
7. Minkowski H. Dichteste gitterförmige Lagerung // Nachr. Ges. Wiss. – Göttingen, 1904. – P. 311–355.
8. Zoutendijk G. Methods of feasible directions: a study in linear and nonlinear programming. – Amsterdam:
Elsevier, 1960. – 126 p.
Поступило в редакцию 11.09.2008Институт проблем машиностроения
им. А.Н. Подгорного НАН Украины, Харьков
Corresponding Member of the NAS of Ukraine Yu.G. Stoyan, V. N. Patsuk
A method of covering a convex polyhedral region by a minimal number
of congruent spheres
The problem is reduced to a sequence of sphere radius minimization problems when fixing the number
of spheres. The objective function is the minimum of a finite number of convex smooth functions.
It is shown that the extrema are reached at the vertices of the Voronoi polyhedra constructed for
the centers of the spheres. The method of feasible directions in combination with a random search
is applied for searching the extrema. A number of numerical examples is given.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2009, №5 45
|
| id | nasplib_isofts_kiev_ua-123456789-8507 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-01T15:15:59Z |
| publishDate | 2009 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Стоян, Ю.Г. Пацук, В.Н. 2010-06-04T14:43:03Z 2010-06-04T14:43:03Z 2009 Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров / Ю. Г. Стоян, В.Н. Пацук // Доп. НАН України. — 2009. — № 5. — С. 41-45. — Бібліогр.: 8 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/8507 517 Задача зводиться до низки задач мiнiмiзацiї радiуса куль при фiксованiй їх кiлькостi. Функцiя мети являє собою мiнiмум скiнченної кiлькостi опуклих гладких функцiй. Показано, що екстремуми досягаються у вершинах багатогранникiв Вороного, побудованих для центрiв куль. Для знаходження екстремумiв застосовується метод можливих напрямкiв у комбiнацiї з випадковим пошуком. Наведено низку чисельних прикладiв. The problem is reduced to a sequence of sphere radius minimization problems when fixing the number of spheres. The objective function is the minimum of a finite number of convex smooth functions. It is shown that the extrema are reached at the vertices of the Voronoi polyhedra constructed for the centers of the spheres. The method of feasible directions in combination with a random search is applied for searching the extrema. A number of numerical examples is given. ru Видавничий дім "Академперіодика" НАН України Математика Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров A method of covering a convex polyhedral region by a minimal number of congruent spheres Article published earlier |
| spellingShingle | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров Стоян, Ю.Г. Пацук, В.Н. Математика |
| title | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров |
| title_alt | A method of covering a convex polyhedral region by a minimal number of congruent spheres |
| title_full | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров |
| title_fullStr | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров |
| title_full_unstemmed | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров |
| title_short | Метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров |
| title_sort | метод покрытия выпуклого многогранного множества минимальным количеством одинаковых шаров |
| topic | Математика |
| topic_facet | Математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/8507 |
| work_keys_str_mv | AT stoânûg metodpokrytiâvypuklogomnogogrannogomnožestvaminimalʹnymkoličestvomodinakovyhšarov AT pacukvn metodpokrytiâvypuklogomnogogrannogomnožestvaminimalʹnymkoličestvomodinakovyhšarov AT stoânûg amethodofcoveringaconvexpolyhedralregionbyaminimalnumberofcongruentspheres AT pacukvn amethodofcoveringaconvexpolyhedralregionbyaminimalnumberofcongruentspheres |