WikiSort.ru - Не сортированное

Простой алгоритм

Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек ${\displaystyle p}$ и ${\displaystyle q}$ .

Этот перпендикуляр разбивает плоскость на две полуплоскости ${\displaystyle H_{pq}}$ и ${\displaystyle H_{qp}}$ , причём область Вороного точки p целиком содержится в одной из них, а область точки ${\displaystyle q}$  — в другой. Область Вороного ${\displaystyle V_{p}}$ точки ${\displaystyle p}$ совпадает с пересечением всех таких полуплоскостей ${\displaystyle H_{pq}}$ :

${\displaystyle V_{p}=\bigcap \limits _{q\in S/\{p\}}H_{pq}}$ .

Таким образом, решение задачи сводится к вычислению такого пересечения для каждой точки ${\displaystyle p}$ . Алгоритм может быть реализован с вычислительной сложностью ${\displaystyle O(n^{2}\log n)}$ .

Алгоритм Форчуна

Алгоритм основан на применении заметающей прямой. Заметающая прямая — это вспомогательный объект, представляющий собой вертикальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного, прямой и областями точек состоит из отрезков парабол (так как геометрическое место точек, равноудалённых от заданной точки и прямой — это парабола). Прямая движется слева направо. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы. Добавление точки к диаграмме при использовании двоичного дерева поиска имеет сложность ${\displaystyle O(\log n)}$ , всего точек ${\displaystyle n}$ , а сортировка точек по ${\displaystyle x}$ -координате может быть выполнена за ${\displaystyle O(n\log n)}$ , поэтому вычислительная сложность алгоритма Форчуна равна ${\displaystyle O(n\log n)}$ .

Рекурсивный алгоритм

Основная идея рекурсивного алгоритма заключается в использовании метода динамического программирования. Исходное множество точек ${\displaystyle S}$ разбивается на два подмножества ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$ , для каждого из них строится диаграмма Вороного, а затем полученные диаграммы объединяются в одну. Разбиение множества ${\displaystyle S}$ осуществляется при помощи прямой, разделяющей плоскость на две полуплоскости, так, чтобы в обеих полуплоскостях находилось примерно одинаковое количество точек. Объединение диаграмм Вороного множеств ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$ может быть выполнено за время ${\displaystyle O(n)}$ , поэтому вычислительная сложность алгоритма равна ${\displaystyle O(n\log n)}$ .