Comments 6
Что насчёт оптимальности предложенных для примера алгоритмов?
Доказать применимость можно для любого алгоритма, но эффективно решать задачу это не позволит. Для эффективности требуется нечто большее. Есть это нечто в описываемой структуре?
В примерах видим два этапа - построение структуры из статьи, а затем использование структуры в дополнительном алгоритме. Есть аналогичное по применимости множество индексных структур, позволяющих делать то же самое, но с доказанной оптимальностью (вычислено О большое и показано, что оно лучше других). Чем индексы хуже предложенной структуры? Точнее - собственно индексирование должно быть менее затратным в случае, если структура из статьи действительно полезна. Хотя возможно уменьшение затрат второго этапа при худших показателях первого. Но эти вопросы автор не осветил. А стоит подумать.
Что насчёт оптимальности предложенных для примера алгоритмов?
Вы хотите доказательство, что не бывает решения быстрее O(n log n) для приведенных задач? Это доказать обычно весьма сложно. Редко кто вообще заморачивается давать нижнюю оценку сложности для решения задачи.
Тут во всех задачах можно показать, что решения быстрее O(n) не бывает, ибо надо будет все точки обработать, но доказать, что нет каких-нибудь решений за O(n log log n) я не могу.
Так-то я привел весьма эффективные решения задач. Всякие альтернативы работают за O(n^2).
Есть аналогичное по применимости множество индексных структур, позволяющих делать то же самое, но с доказанной оптимальностью (вычислено О большое и показано, что оно лучше других)
Во-первых, структуры-то есть, но как их к этим задачам применять - непонятно. Какое-нибудь R-дерево или квадро-дерево тут слабо применимы. Двумерные деревья отрезков - тоже. В первых двух задачах их еще можно использовать для остечения заведомо далеких точек, да, но там нет гарантии O(log n) для поиска ближайшей точки.
В первых двух задачах можно еще использовать иерархическую структуру на основе диаграммы Вороного же, но там тоже будет O(n log n), эта структура сильно сложнее, и она не применима в остальных задачах.
Во-вторых, про "показано, что оно лучше других" - это как? Приведите пример, что ли? Повторюсь, редко где вообще доказывает нижнию оценку сложности.
Хотя возможно уменьшение затрат второго этапа при худших показателях первого. Но эти вопросы автор не осветил.
В смысле, не ответил? Я привел решения за O(n log n) включая и триангуляцию и основной алгоритм. Тут зачастую самое медленное - построение триангуляции Делоне. Вторая часть в этих задачах работает или за O(n) или O(n log n). Это вместо O(n^2), если не использовать триангуляцию Делоне. Я не акцентрировал внимание на оценке сложности второй части, потому что это стандартные или вообще тривиальные алгоритмы.
Я пропустил или не нашел - а всегда ли существует триангуляция Делоне?
Конечно, всегда существует. Это проще понять, если рассмотреть диаграмму Вороного. Очевидно же, что плоскость можно разбить на ячейки, где точки в каждой - геометрическое множество точек, ближе к одной из конечного множества S, чем к любой другой.
А триангуляцию Делоне можно построить по диаграмме Вороного. Не всегда однозначно, правда, если больше трёх ячеек соседствуют по вершине.
Там треугольник будет из центров ячеек с общей вершиной на границе, а центр описанной окружности - эта самая вершина. И она по свойствам Диаграммы будет равноудалена от этих трех центров и все остальные точки из S будут не ближе к этой вершине, чем эти три. А значит, ни одна другая точка не лежит внутри окружности.
Интересная статья.
Свойство можно доказать ещё так (не знаю, будет ли более красиво).
Если отрезок АВ не попал в триангуляцию, то среди точек есть точка С, такая что |АС| < |АВ|, и |СВ| < |АВ|, в противном случае середина отрезка АВ была бы на границе между соседними ячейками Вороного с центрами в А и В (в этом легко убедиться, построив круги радиуса АВ в центрах А и В, тогда т.С должна быть внутри пересечении этих кругов).
Ну а теперь доказательство для АВ свелось к доказательству для двух более коротких отрезков. АС (и ВС) либо есть в триангуляции, либо аналогично доказывается через более мелкие отрезки, по индукции.
Об одном интересном свойстве триангуляции Делоне