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

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

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

Ближайшая к точке А точка В соответствует ближайшему ребру (границе области близости). Доказательство:

|AT| > |AP|

|AP| = |AB|/2

|AT| < |AX|/2

|AX| > 2|AT| > 2|AP| = |AB|

Время поиска ближайшей к А точки - O(n). Для отыскания пары ближайших точек каждое ребро рассматривается один раз. Их количество O(n), следовательно время решения тоже O(n).