Доброго всем времени суток, уважаемые посетители сайта Хабрахабр. В данной статье я бы хотел рассказать вам о том, что такое диаграмма Вороного (изображена на картинке ниже), о различных алгоритмах её построения (за ![][1], ![][2] — пересечение полуплоскостей, ![][3] — алгоритм Форчуна) и некоторых тонкостях реализации (на языке C++).

[![][4]][5]

Также будет рассмотрено много интересных применений диаграммы и несколько любопытных фактов о ней. Будет интересно!
[Читать дальше →][6]

[1]: https://habrastorage.org/getpro/habr/post_images/779/d1d/ce6/779d1dce68f0e915837b5e3686dd33a1.gif "O(n^4)"
[2]: https://habrastorage.org/getpro/habr/post_images/06c/fca/fd3/06cfcafd30903e22872fa03ce2bd746e.gif "O(n^2*log(n))"
[3]: https://habrastorage.org/getpro/habr/post_images/0ed/5cf/b0b/0ed5cfb0b42f9409c4fdcd8939d74e9b.gif "O(n*log(n))"
[4]: https://habrastorage.org/files/b40/0a5/4aa/b400a54aa65b461f92fe802acee5ac40.jpg
[5]: https://habrahabr.ru/post/309252/
[6]: https://habrahabr.ru/post/309252/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut