1. Насколько я понял, автор не знает, что такое вычислительная сложность вообще. Тут я предложил википедию: как мне кажется, для начала ее вполне хватит.
2. Расчет вычислительной сложности триангуляции Делоне описывается у того же Скворцова (хотя на мой взгляд лучше читать книгу по вычислительной геометрии де Берга, Овермарса и др.). И таки да, среднее число флипов действительно равно O(1). Это выглядит достоверным даже на первый взгляд: степень вершин триангуляции в среднем равна шести (следствие теоремы Эйлера), хотя, конечно, строгое доказательство несколько сложнее.
Что касается сортировки точек в лексикографическом порядке — фактически в алгоритмах триангуляции Делоне заметающей прямой базовый шаг производит сортировку точек. Суммарные затраты на выталкивание точки из очереди с приоритетом и будут давать этот O(N*log N). Модификация алгоритма, использующая начальную сортировку тривиальна и никакого значения не имеет.
3. Позанудствую, конечно, но, строго говоря, для выпуклой оболочки точек плоскости верхняя граница вычислительной сложности O(N log H), где H — число вершин выпуклой оболочки. См. алгоритм Чена.
Да, каюсь, пролетел мимо комментария, где вы пользуетесь комплексными числами для сумм углов, и мысль пошла в сторону тригонометрии.
Забавно: если раскрыть скобки в вашем выражении для сумм углов через комплексные числа, получится ровно та же формула, что и у автора статьи и в определителе системы координат аффинного пространства. Этого, конечно, следовало ожидать. В любом случае, число операций везде будет одинаковым (с точностью до расстановки скобок).
Углы не проще: точно сравнить сумму углов со 180 градусами будет очень сложно, а неточные сравнения могут привести к трэшу в результирующем ответе. Посмотрите, например, статью Шевчука: Adaptive precision arithmetic. Мы с вами здесь же на Хабре, вроде, обсуждали мою статью как раз на эту тему :)
Триангуляция Делоне для отрезков строится проще, чем диаграмма Вороного для отрезков. Вычислительная сложность алгоритмов, конечно, одинакова (я не имею в виду предложенный автором статьи алгоритм).
Имеется в виду, что если запустить алгоритм построения триангуляции Делоне на множестве отрезков, то результатом будет фактически триангуляция выпуклой оболочки множества отрезков. Значит, у вас, скорее всего, появятся лишние диагонали, их нужно будет убрать. Это делается за линейное время (O(N)).
С вычислительной сложностью имеет смысл разобраться (почитайте, например, статью в википедии). Просто предлагать оптимизации к кубическому алгоритму для решения задачи при условии, что она решается за O(N log N) так же странно, как, например, пытаться где-то экономить копейки при регулярных бессмысленных милионных тратах :) Это не имхо. Вы можете попытаться прикинуть ожидаемую вычислительную сложность (как бы для «среднего случая»), но сделать это будет достаточно сложно, а в вашем случае, по-видимому, и бесполезно.
Пожалуйста. Вообще, эти рассуждения показывают связь между триангуляцией Делоне и выпуклой оболочкой: триангуляция Делоне — это проекция выпуклой оболочки спроецированных на параболоид исходных точек.
А что насчет вычислительной сложности предложенного вами алгоритма?
1. Вы описали что-то очень похожее на ушную триангуляцию. Насколько я понимаю, в худшем случае у вас время работы алгоритма кубическое (ушную триангуляцию, правда, можно довести до квадратичного времени). Если я прав, то все очень печально: триангуляция Делоне с ограничениями (constrained Delaunay triangulation) работает за O(N log N), а избавиться от лишних диагоналей можно за линейное время. Или я невнимательно прочитал вашу статью?
2. Критерий Делоне проверяется в библиотеках вычислительной геометрии исходя из следующих соображений: представьте себе треугольник T на плоскости P. Погрузим эту плоскость в трехмерное пространство и возьмем ортонормированную систему координат, в которой два орта лежат на плоскости P. Допустим, это будут орты x и y. Орт z, соответственно, будет перпендикулярен плоскости P. Рассмотрим параболоид z = r^2, где r — радиус-вектор точки на плоскости (линейная комбинация x и y). Оказывается, что любая окружность на плоскости, спроецированная на такой параболоид будет содержаться в некоторой плоскости, секущей параболоид на две части. Соответственно, точка, лежащая внутри окружности, будет ниже плоскости, а точка вне окружности — выше. Учитывая, что точки треугольника лежат на описанной около этого треугольника окружности, легко составить предикат, проверяющий критерий Делоне для четырех точек: это будет знак определителя системы координат, составленной из этих точек, спроецированных на параболоид в трехмерном пространстве. В общем, расписав определитель такой матрицы (это просто выписанные построчно однородные координаты точек), вы получите свой же результат с той лишь разницей, что он обобщается на Евклидовское пространство любой конечной размерности :)
Вообще, рекомендую воспользоваться библиотекой вычислительной геометрии, чтобы не искать множество любопытных ошибок (например, связанных с устойчивостью вычислений). Попробуйте посмотреть на CGAL или LEDA.
В общем случае проверка на равенство с нулем ничего не дает: вероятность того, что три произвольные точки лежат на одной прямой, ничтожна. А как посчитать знак выражения в модульной арифметике, я пока представить не могу.
Вообще, смысл статьи как раз в том, что подавляющее большинство ответов будут определяться floating-point арифметикой, а до последнего шага (который вовсе не обязательно считать в рациональной арифметике, есть множество относительно быстрых алгоритмов) дойдет несколько входов из сотен миллионов. То есть среднее время будет очень близко к минимальному.
2. Расчет вычислительной сложности триангуляции Делоне описывается у того же Скворцова (хотя на мой взгляд лучше читать книгу по вычислительной геометрии де Берга, Овермарса и др.). И таки да, среднее число флипов действительно равно O(1). Это выглядит достоверным даже на первый взгляд: степень вершин триангуляции в среднем равна шести (следствие теоремы Эйлера), хотя, конечно, строгое доказательство несколько сложнее.
Что касается сортировки точек в лексикографическом порядке — фактически в алгоритмах триангуляции Делоне заметающей прямой базовый шаг производит сортировку точек. Суммарные затраты на выталкивание точки из очереди с приоритетом и будут давать этот O(N*log N). Модификация алгоритма, использующая начальную сортировку тривиальна и никакого значения не имеет.
3. Позанудствую, конечно, но, строго говоря, для выпуклой оболочки точек плоскости верхняя граница вычислительной сложности O(N log H), где H — число вершин выпуклой оболочки. См. алгоритм Чена.
Забавно: если раскрыть скобки в вашем выражении для сумм углов через комплексные числа, получится ровно та же формула, что и у автора статьи и в определителе системы координат аффинного пространства. Этого, конечно, следовало ожидать. В любом случае, число операций везде будет одинаковым (с точностью до расстановки скобок).
С вычислительной сложностью имеет смысл разобраться (почитайте, например, статью в википедии). Просто предлагать оптимизации к кубическому алгоритму для решения задачи при условии, что она решается за O(N log N) так же странно, как, например, пытаться где-то экономить копейки при регулярных бессмысленных милионных тратах :) Это не имхо. Вы можете попытаться прикинуть ожидаемую вычислительную сложность (как бы для «среднего случая»), но сделать это будет достаточно сложно, а в вашем случае, по-видимому, и бесполезно.
А что насчет вычислительной сложности предложенного вами алгоритма?
1. Вы описали что-то очень похожее на ушную триангуляцию. Насколько я понимаю, в худшем случае у вас время работы алгоритма кубическое (ушную триангуляцию, правда, можно довести до квадратичного времени). Если я прав, то все очень печально: триангуляция Делоне с ограничениями (constrained Delaunay triangulation) работает за O(N log N), а избавиться от лишних диагоналей можно за линейное время. Или я невнимательно прочитал вашу статью?
2. Критерий Делоне проверяется в библиотеках вычислительной геометрии исходя из следующих соображений: представьте себе треугольник T на плоскости P. Погрузим эту плоскость в трехмерное пространство и возьмем ортонормированную систему координат, в которой два орта лежат на плоскости P. Допустим, это будут орты x и y. Орт z, соответственно, будет перпендикулярен плоскости P. Рассмотрим параболоид z = r^2, где r — радиус-вектор точки на плоскости (линейная комбинация x и y). Оказывается, что любая окружность на плоскости, спроецированная на такой параболоид будет содержаться в некоторой плоскости, секущей параболоид на две части. Соответственно, точка, лежащая внутри окружности, будет ниже плоскости, а точка вне окружности — выше. Учитывая, что точки треугольника лежат на описанной около этого треугольника окружности, легко составить предикат, проверяющий критерий Делоне для четырех точек: это будет знак определителя системы координат, составленной из этих точек, спроецированных на параболоид в трехмерном пространстве. В общем, расписав определитель такой матрицы (это просто выписанные построчно однородные координаты точек), вы получите свой же результат с той лишь разницей, что он обобщается на Евклидовское пространство любой конечной размерности :)
Вообще, рекомендую воспользоваться библиотекой вычислительной геометрии, чтобы не искать множество любопытных ошибок (например, связанных с устойчивостью вычислений). Попробуйте посмотреть на CGAL или LEDA.
Вообще, смысл статьи как раз в том, что подавляющее большинство ответов будут определяться floating-point арифметикой, а до последнего шага (который вовсе не обязательно считать в рациональной арифметике, есть множество относительно быстрых алгоритмов) дойдет несколько входов из сотен миллионов. То есть среднее время будет очень близко к минимальному.
Может, я неверно понял ваш комментарий?