Рассмотрим следующую задачу: есть почтовые службы pi, мы хотим знать, какую область плоскости обслуживает каждая. При этом каждую точку q обслуживает та служба, которая ближе. Ответ на этот и ряд других вопросов, связанных с близостью на плоскости, дает диаграмма Вороного. Диаграмма Вороного изображена на рисунке выше. Она состоит из вершин(v) диаграммы и ее сторон(e). Формальное определение: Пусть P - множество из n различных точек плоскости Диаграмма Вороного - деление плоскости на n ячеек, по одной на каждую точку P Точка q принадлежит ячейке, относящейся к pi из P, если расстояние от q до pi меньше, чем расстояние от q до любой другой точки P. Можно провести очень интересную аналогию из области кристаллографии. Предположим, что точки представляются в виде зерен кристалла, которые растут с постоянной скоростью во всех направлениях. Предположим также, что рост зерен кристалла продолжается до тех пор, пока два или более зерен не встретятся. Через некоторое достаточное время каждое выросшее зерно будет представлено в виде ячейки диаграммы Вороного для своего ядра(вполне очевидно, что рост крайних неограниченных областей может продолжаться бесконечно). В результате будет получена диаграмма Вороного для множества P. Весьма забавно представить более быстрый процесс роста в одном из направлений и при расположении ядер в фиксированных точках в пространстве. Полученная в результате диаграмма Вороного в трехмерном пространстве будет состоять из ограниченных и неограниченных полиэдральных областей. Диаграмма Вороного аналогично определяется для n-мерного пространства.  8  Комментарии к статье  8 8  Обсудить в чате