За я умею без всяких вороновых, но немного не так как ты говоришь. Мне интересно как можно пересекая полуплоскости построить вороного за O(n²)? Как это сделать совсем втупую: фиксируем точку, строим O(n) срединных перпендикуляров между нашей точкой и всеми остальными, всех их пересекаем, получаем O(n²) точек, далее за O(n) проверяем каждую точку на принадлежность каждой полуплоскости — профит за O(n³) построили ячейку вороного. Как построить ячейку за O(n)? (P.S. ни диаграмму вороного, ни пересечение полуплоскостей ни разу не писал, мне не понятно как пересечь n полуплоскостей за O(n))