ВУЗ:
Составители:
Рубрика:
Глава 2. Плоские и планарные графы 69
угольникам Вороного. Рассмотренный способ построения диаграм-
мы, который не является единственным, предполагает наличие три-
ангуляции Делоне на множестве S. Отметим, что диаграмма Вороно-
го строится на плоскости, поэтому ячейки V(i), соответствующие
вершинам выпуклой оболочки M
k
, являются неограниченными.
Соседями назовем центры тех ячеек Дирихле – Вороного, кото-
рые имеют общую сторону с ячейкой для Р
i
. Например, на рис. 2.25
ячейка Дирихле имеет пять соседей.
Координаты вершин ячейки V(i), являющиеся центрами соответ-
ствующих описанных окружностей, можно определить через коор-
динаты соседей и точки Р
i
. Уравнение окружности, проходящей, на-
пример, через точки с координатами
(
)
11
,
x
y ,
(
)
22
,
x
y ,
(
)
33
,
x
y , мож-
но записать в виде
22
22
1111
22
2222
22
3333
1
1
0
1
1
xy xy
xyxy
xyxy
xyxy
+
+
=
+
+
Или, разлагая определитель по первой строке, получим другую за-
пись уравнения окружности:
()
22
0ax y bx cy d+−+−=,
где
22
11 1
11
22
22 22 2
22
33
333
1
1
1, 1
1
1
xyy
xy
axy bxyy
xy
xyy
+
==+
+
,
22 22
111 1111
22 22
222 2222
22 22
333 3333
1
1,
1
x
yx xyxy
cxyx dxyxy
x
yx xyxy
++
=+ =+
++
.
Тогда
22
22
2
4
22
4
bcadbc
xy
aa
a
++
⎛⎞⎛⎞
−++=
⎜⎟⎜⎟
⎝⎠⎝⎠
Страницы
- « первая
- ‹ предыдущая
- …
- 67
- 68
- 69
- 70
- 71
- …
- следующая ›
- последняя »
