Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
6.3. Обобщения диаграммы ЗП
Вороного плоскостью, содержащей г-ось и некоторую точку множества S\ (рис. 6.18(b)). (Читатель может легко воспроизвести опущенные здесь детали.) Поэтому, хотя диаграмма Вороного содержит O(N) областей, она может иметь 0(№) вершин и ребер. Позже Кли [Klee (1980)] развил эту идею для пространств произвольной размерности d. Полученный результат сформулирован в следующей теореме:
Теорема 6.13. M(d, N) —максимальное число вершин диаграммы Вороного множества из N точек в d-мерном пространстве удовлетворяет условию
ГОД /гг<"2т < М (d, ЛГ) < 2 (\йЩ яг<№|) для четных d и условию
(rrf/2l-l)l _ nrd,2l ^M(d> N)< r/d/211 nrwi
для нечетных d.
Экспоненциальный рост сложности диаграммы Вороного раскрывает любопытное сходство с поведением выпуклых оболочек в пространствах большой размерности. Это сходство, как впервые заметил Браун [Brown (1979b)], имеет глубокие корни, которые со всей очевидностью проявляются в контексте преобразования инверсии, описанного в разд. 6.3.1.1.
Не теряя общности, рассмотрим диаграммы Вороного на плоскости. Пусть S = {pi, Pn}—множество из N точек,
лежащих в плоскости 2=1 пространства ?3, С —образ этой плоскости при преобразовании инверсии в Е3, aS' = {pp..., • ••» Pn} ~~ образ множества S при инверсии (точки множества S' лежат на С, pt и р\ являются образами друг друга). Рассмотрим выпуклую оболочку CH(S') множества S' и разобьем ее на две части, которые будем называть дальней стороной и ближней стороной в зависимости от того, «видны» или нет их точки из начала координат (на рис. 6.19 показан двумерный аналог ситуации).
Пусть я — плоскость, содержащая грань F оболочки CH(S'), определяемую тремя точками: р[, р'2 и р'ъ (предполагается, что многогранник CH(S') является симплициальным, т. е. каждая его грань является треугольником). Сфера С (л), являющаяся образом плоскости л при инверсии, проходит через точки О, Ри Рч и рз и пересекает плоскость z = 1 по окружности, определяемой точками pi, р2 и р3. В зависимости от того, принадлежит F ближней или дальней стороне оболочки CH(S'), будем различать два случая:
312
Гл. 6. Близость: варианты и обобщения
(1) F принадлежит ближней стороне оболочки CH(S').B этом случае полупространство, определяемое плоскостью я и не содержащее начала координат, не содержит внутри ни одной точки множества S'. Так как это полупространство отображается внутрь сферы С (я), то окружность, проходящая через точки р\, Р2 и рз, является окружностью Делоне, центр которой является вершиной диаграммы Vori(S). Таким образом, каждая грань ближней стороны оболочки CH(S') определяет треугольник в
Ближняя
Рис. 6.19. Пример, иллюстрирующий связь выпуклых оболочек с диаграммами Вороного. Ближняя сторона выпуклой оболочки conv(5*) показана сплошным отрезком, а дальняя — штриховыми.
триангуляции Делоне множества 5 (и с учетом двойственности вершину диаграммы Vor^S)).
(2) F принадлежит дальней стороне оболочки CH(S'). Снова полупространство, определяемое плоскостью я и не содержащее начала координат, отображается внутрь сферы С (л). Однако в этом случае полупространство содержит внутри N— 3 точек множества 5", так что окружность, проходящая через точки ри р2 и р3, содержит внутри N — 3 точек множества 5. Отсюда следует, что центр этой окружности является вершиной диаграммы Вороного дальней точки множества S1).
Это наблюдение не только устанавливает тесную связь между диграммами Vori(S) и VorN-i(S), но также связывает диаграмму Вороного ближней точки множества из N точек в d-мерном пространстве с выпуклой оболочкой N точек, лежа-
') В предположении, что никакие четыре точки множества 5 не лежат на одной окружности, окружность, являющаяся пересечением сферы С (я) и плоскости 2=1, проходит в точности через три точки множества S. Соответственно грань F определяется образами этих трех точек и никакими другими точками множества S', а это значит, что F является треугольником (a CH(S)-симплициальным политопом).
6.4. Промежутки и покрытия
313
щих на поверхности сферы в (d -4- 1)-мерном пространстве. Следовательно, можно воспользоваться существующими методами построения выпуклых оболочек в многомерных пространствах (см. разд. 3.3) для получения многомерных диаграмм Вороного. Соответствующая работа была выполнена Эйвисом и Бхатачарья [Avis, Bhattacharya (1983)] и Зейделем [Seidel (1982)].
6.4. Промежутки и покрытия
Рассмотрим теперь очень важный класс задач о близости, который мы коротко назвали «промежутки и покрытия». Промежутки — это шары (в случае плоскости это круги), не содержащие точек заданного множества, а покрытия — это множества шаров, объединение которых содержит все точки заданного множества. Начнем со следующей задачи:
Задача Б.П (НАИМЕНЬШАЯ ОХВАТЫВАЮЩАЯ ОКРУЖНОСТЬ)1). На плоскости заданы N точек. Найти наименьшую окружность, охватывающую все заданные точки.
Это классическая задача, которой посвящена обширная литература. Поиск эффективного алгоритма решения этой задачи начался, по-видимому, в 1860 г. [Sylvester (I860)]. Наименьшая охватывающая окружность единственна, и, кроме того, она либо является описанной окружностью для некоторой тройки точек заданного множества, либо некоторая пара точек заданного множества служит диаметром этой окружности [Rade-macher, Toeplitz (1957), с. 16]. Таким образом, существует прямой алгоритм решения этой задачи, который перебирает все пары и тройки точек множества, строит определяемые ими окружности и выбирает среди них наименьшую, охватывающую при этом все исходное множество точек. Непосредственная реализация этой процедуры дала бы алгоритм со сложностью 0(iV4). Елзинга и Хирн [Elzinga, Hearn (1972а, 1972b)] улучшили этот метод, получив алгоритм со сложностью 0(N2).
