Вопрос по областям Вороного.

[undefined]

но как осуществляется эта проверка?

не проверял, но вроде должно быть верно:
-Выбираем точку из множества
-Ставим затравку, считая, что ячейкой Вороного для данной точки будет вся плоскость.
-Проводим отрезки от точки до всех остальных точек множества
к каждому отрезку проводим серединный перпендикуляр
-Каждый перпендекуляр разбивает плоскость на 2 полуплоскости, надо выбрать ту полуплоскость где НЕ находится наша точка и вычесть полученное множество из текущей ячейки, т.о. на каждом шаге ячейка по площади будет становится все меньше и после обработки последнего отрезка получим готовую ячейку Вороного для данной точки.
Далее повторяем вышенаписаное для всех точек множества.

И как описываются эти зоны, чтобы потом можно было осуществлять проверки?

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