Использование диаграмм воронова в задачах компьютерной геометрии.

  • 07 апр. 2012 г.
  • 1337 Слова
Использование диаграмм Воронова в задачах компьютерной геометрии.



























Вороной Георгий Феодосьевич 
(28 апреля 1868 – 20 ноября 1908) – российский математик украинского происхождения. Родился в селе Журавка, ныне Варвинского района Черниговской области. 
Учился в Санкт-Петербургский университете у АндреяМаркова. В 1894 году защитил магистерскую диссертацию на тему «О целые числа, зависящие от корня уравнения третьей степени». В том же году был избран профессором Варшавском университете, где изучал цепные дроби. В 1897 году защитил докторскую диссертацию на тему «О одно обобщение алгоритма непрерывных дробей», удостоенную премии имени Буняковского. В Варшаве в Вороного обучался Вацлав Серпинский. Умер в родном селе от желчекаменная болезни. 
Знаменитая теорема Вороного о паралелоедры: всякий примитивный паралелоедр аффинных эквивалентен DV-области некоторых решеток. В честь Вороного названы диаграммы Вороного, применяемых в информатике. 
Истинное значение начатых им в конце прошлого – начале нынешнего века новых направлений в области теория чисел раскрывается лишь в наше время.Труды Георгия Вороного приобрели особенно большое значение за последние двадцать лет. Это связано с развитием компьютерной графики, молекулярной биологии, радиационной физики, космологии, созиданием искусственного интеллекта За свою короткую (40 лет) жизнь Г. Вороний написал всего 12 научных работ, но 8 из них успешно используются именно сейчас. Это – уникальное явление, в частности вматематике, где любые открытие уже через 2-3 года считаются устаревшими. 

Диаграмма Вороного 

Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множеств

Можно провести аналогию из областикристаллографии. Предположим, что точки представляются в виде зерен кристалла, которые растут с постоянной скоростью во всех направлениях. Предположим также, что рост зерен кристалла продолжается до тех пор, пока два или более зерен не встретятся. Через некоторое достаточное время каждое выросшее зерно будет представлено в виде ячейки. В результате будет получена Диаграмма Вороного.


[pic]








Смыслразбиения элементарен.
У нас есть плоскость, на которой мы должны поставить конечное множество точек (как минимум, две).
Эти точки зададут разбиение плоскости на области, в каждой из которых любая точка будет более близка к своей выделенной точке. Это лучше показать на картинке.
Для двух точек это, как нетрудно догадаться, выглядит так:
[pic]
(Граница — серединный перпендикуляротрезка, соединяющего эти точки).
Для трех точек получим:
1. [pic] 2. [pic]
Для четырех:
1. [pic] 2.[pic]
И так далее.
Таким образом, любое конечное множество точек на плоскости задаст разбиение на области, в каждой из которых будут находиться точки, лежащие ближе к данной точке, чем к какой бы то ни было другой.






[pic]


При разбиении плоскости такого рода у нас получаютсятолько выпуклые многоугольники.Получаются они по следубщей причине.


Возможны две разные ситуации:
Когда в невыпуклый многоугольник "врезается" один выпуклый, или когда несколько (именно в вогнутую часть): 
[pic]
Если с первым случаем легко доказать противоречие, то во втором надо чуть-чуть подумать.
Оно-то "видно", но как доказать строго?
[pic]





Между каждыми двумя точками проходитсерединный перпендикуляр к соединяющему их отрезку, поэтому вогнутости получиться в принципе не может.
































Алгоритмы построения


Простой алгоритм

Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек p и q. Этот перпендикуляр разбивает плоскость на две...
tracking img