![image][1]


Недавно, на хабрахабре была опубликована [статья][2], целиком и полностью посвященная диаграммам Вороного. В статье автор подробно описывает алгоритм Форчуна, применяемый для построения Диаграммы Вороного за **O(n\*log(n))**. Стоит отметить, что описание этого алгоритма ни раз появлялось в рунете, в то время как о других алгоритмах(с той же асимптотикой) рассказано ровным счетом ничего. Данная статья исправляет это _недоразумение_, а также является отличным дополнением к уже опубликованному ранее материалу.
Ниже, я расскажу о алгоритме **_'разделяй и властвуй'_** построения диаграммы Вороного за **O(n\*log(n))**, а также, основываясь на своем практическом опыте, о по-настоящему крутых штуках, в которых это применимо. Вообще, алгоритмы типа _'разделяй и властвуй'_ являются своего рода классикой программирования(думаю, про сортировку данным методом слышал каждый программист), хорошо параллелятся и легко читаются(если, конечно, знать основную идею алгоритма).
[Читать дальше →][3]

[1]: https://habrastorage.org/getpro/habr/post_images/316/a63/52f/316a6352f962702a0e28a8fd5168068c.jpg
[2]: https://habrahabr.ru/post/309252/
[3]: https://habrahabr.ru/post/314852/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut