18. Задача о близости. Области близости. Определение диаграммы Вороного.
Область близости для точки А – это множество всех точек плоскости, более близких к точке А, чем к любой другой точке множества. Область близости – это всегда выпуклый многоугольник; она не обязательно ограничена.
Диаграмма Вороного – совокупность областей близости, построенных для каждой точки множества. Представляет из себя планарный граф. При построении диаграммы Вороного происходит разбиение пространства на области, которые не пересекаются.
Ближайшая к точке А точка В соответствует ближайшему ребру (границе области близости). Доказательство:
|AT| > |AP|
|AP| = |AB|/2
|AT| < |AX|/2
|AX| > 2|AT| > 2|AP| = |AB|
Время поиска ближайшей к А точки - O(n). Для отыскания пары ближайших точек каждое ребро рассматривается один раз. Их количество O(n), следовательно время решения тоже O(n).