25. Область близости.

Область близости для точки А – это множество всех точек плоскости, более близких к точке А, чем к любой другой точке множества. Область близости – это всегда выпуклый многоугольник; она не обязательно ограничена.

Пусть точки всего 2 А и В.Область близости для А-полуплоскость полученная делением плоскости прямой, перпендикулярной отрезку АВ и проходящей через его середину. Если ввести С то для нее будет справедливо тоже самое. Результатом, т.е областью близости будет пересечение полуплоскостей с В и С, а в общем случае –пересечение полуплоскостей близости относительно всех остальных точек. Полученная фигура не обязательно должна быть конечной(ее сторонами Мб и отрезки и лучи),но все равно ее зовут многоугольником близости. Он обязательно выпуклый ,т.к. пересечение выпуклых множеств тоже выпуклое. Если 2 точки совпадают то области близости у них нет.

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