Comments 48
На самом деле, особенностью конкретно этой задачи является геометрическая часть. Конкретно условия, что отрезки не пересекаются и никакие три точки не лежат на одной прямой. Данные условия сложно формализовать и описать в терминах SQL, поэтому я думаю, что это просто похожая задача.
Данные условия сложно формализовать и описать в терминах SQL
Это неверно. Есть spatial datatype и целая пачка GIS-функций, которые позволяют хранить точки, комбинировать их в отрезки и проверять отрезки на пересечение. Скажем, та же ST_Crosses() проверяет, пересекаются ли две LINESTRING.
А проверка, что никакие три точки не лежат на одной прямой, в общем, и не требуется - формально мы имеем право считать, что условие корректно, и данных, не соответствующих условию, нет. Хотя и проверка - тоже не проблема. Хоть обычной пропорцией, хоть опять же через spatial-функции.
Условия-то как раз формализовать просто, проблема тут в том что это условие на множество всех строк а не на строку, то есть запрос надо делать не относительно таблицы точек, а относительно множества всех подмножеств строк этой таблицы.
Для таких запросов, во-первых, в SQL нет нормальных операторов, а во-вторых, нет алгоритмов оптимизации.
Мне кажется, что ситуацию, когда конец одного отрезка является началом другого, не принято называть пересечением отрезков. Разве отрезки, образующие стороны квадрата, пересекаются? Хотя это всё вопрос договорённости терминологии.
Кажется, в обоих решениях такая ситуация не возникает
Для меня пересечение отрезков - это пересечение множеств их точек. Оно даже обозначается через тот же символ пересечения:
:)
Для задачи это несущественно, потому что доказано существование более строгого решения, когда точки соединяются только попарно. Можно начать доказательство с фразы "докажем, что существует решение, где точки соединяются только попарно", и забыть про ваш случай.
YT видео по подобной задаче, если кому интересно
Я не математик, поэтому вопрос может быть глупый, но переходя от диагоналей к сторонам мы не гарантируем, что из-за этого не появится новое пересечение. Допустим в описаном примере была бы точка внутри треугольника AXD, которая соединялась с другой точкой за пределами ABCD. Меняя AD, на AC мы создаем новое пересечение. Каким образом доказать, что череда таких новых пересечений когда-нибудь закончится?
Каким образом доказать, что череда таких новых пересечений когда-нибудь закончится?
Каждый переход от диагоналей к сторонам уменьшает суммарную длину отрезков, т.е. это нельзя делать до бесконечности.
Строго говоря требуется не просто уменьшение, а уменьшение не меньше чем фиксированная величина. Иначе действительно можно очень долго уменьшать (бесконечно). Но в силу конечности множества точек, а значит и отрезков и разностей расстояния между ними - такая величина безусловно найдётся.
Нет, не надо тут какого-то ограничения на уменьшение. Надо только уменьшение. Тут конечное количество различных паросочетаний синих с красными точек, как вы заметили (n!). Строгое уменьшение длины гарантирует, что мы никогда не вернемся в предыдущее состояние, а значит, этот процесс уменьшения не может длиться бесконечно. Ибо по принципу голубятни, он бы тогда повторял состояния, а этого быть не может.
Берём от единицы вычитаем половину. Потом от остатка ещё половину. И так далее. Результат уменьшается? Через сколько итераций он прекратится уменьшаться?
Тут количество возможных значений бесконечно (1/2^n). В исходном процессе это не так. Различных способов провести отрезки всего n!.
Конечно, можно доказать и через ограничение на минимальное уменьшение и факт, что длина не может быть отрицательной. Но для этого ограничения тоже надо использовать конечность состояний. А раз так, то почему бы не использовать конечность напрямую в доказательстве?
Тут конечное количество различных паросочетаний синих с красными точек
Вы написали ровно то же самое с чем спорите.
Доказательство - это круто, но не менее интересен вопрос об оптимальном алгоритме такого соединения точек. Представленные решения будут явно медленнее O(N^2) в худшем случае.
Алгоритм с разбиением делается за n^2, и это легко показать.
Поиск выпуклой оболочки требует попарного вычисления полярных углов, это n^2, и сами углы можно запомнить (n^2 памяти). После удаления пары точек из выпуклой оболочки нет нужды пересчитывать все углы заново.
Если выпуклая оболочка состоит из точек одного цвета, то спроецируем наши точки на какую-то прямую, и зададим их порядок (прямую можно брать произвольную, в худшем случае на одну точку прямой спроецируются 2 точки множества, порядок для них можно выбрать произвольный).
Поскольку первая и последняя точки по условию одного цвета, найдется такая точка на нашей делящей прямой, слева и справа от которой одинаковое количество красных и синих точек. Проверить этот факт можно за n. Затем рекурсивно вызываем алгоритм для каждого подмножества, так как они гарантировано не пересекаются.
Ну, если считать "в лоб", то получается O(N2 log N), что не сильно-то медленнее "квадрата".
В лоб — это соединить попарно любые точки разного цвета, а потом найти все пересечения отрезков (N^2), в пересекающихся парах поменять точки. Выполнить алгоритм заново с шага поиска пересечений. Как доказать, что число итераций не больше log N?
Делать-то надо как автор написал, это подсчёт я провёл "в лоб".
Выпуклая оболочка строится алгоритмом Грехема за N log N, построить её придётся не более N раз. Всё, время равно O(N2 log N)
Нет, тут итераций может быть очень и очень много. Экспоненциально много. Но можно сразу искать кратчайшее паросочетание, что будет за O(N^3).
Есть очевидное решение за O(N^3) по мотивам авторского доказательства: венгерским алгоритмом, или min-cost-max-flow, находим минимальное по стоимости паросочетание в двудольном графе (цена ребра — длина отрезка). Пересечений там не будет, иначе можно было бы получить более оптимальное паросочетание.
Решение от автора статьи можно реализовать за O(N^2 log N) похоже: N раз строим оболочку за O(N log N). Разбиение на полуплоскости в худшем случае откусит одну пару точек и опять надо N повторений.
Пересчет выпуколой оболочки при удаления одной-двух точек не будет быстрее рассчета всей оболочки заново, похоже.
Разбиение на полуплоскости в худшем случае откусит одну пару точек и опять надо N повторений.
Да, вот в этом вся загвоздка... Подозреваю, что за n*log(n) можно как-то смекнуть удачный угол наклона заметающей прямой, при котором в большинстве случаев получится разбить примерно поровну, и тогда весь алгоритм в идеале займет О(n * log(n)^2)
Не получится О(N * (log N)²) никак, потому что если нам "повезёт" и оболочка каждый раз будет содержать разные цвета — мы будет каждый раз откусывать по 2 точки с повторным построением оболочки, для алгоритма Грехема это даст ϴ (N² log N) как ни исхитряйся.
Тут можно воспользоваться модифицированным алгоритмом Джарвиса и построить сразу одноцветную оболочку, исключая разноцветные пары прямо по ходу алгоритма — но тогда у нас будет ϴ(n (m + h)) на шаге, где m — число построенных пар, а h — число вершин в оболочке. Учитывая что сумма всех m равна исходному N/2 (нам же надо построить все пары!), единственный способ добиться времени меньше чем Ω(N²) — это найти способ гарантированно получать много одноцветных оболочек на начальных этапах разбиения. Но сомнительно что удастся сделать это одновременно разбивая множество каждый раз на близкие по размеру половины.
Мы о разных вещах говорим. Я имел в виду именно заметающую прямую, которую автор статьи использует, если оболочка вышла одноцветной. Оболочки я бы вообще не рассматривал.
Легко доказать, что всегда есть такая прямая, которая может разбить весь набор точек на две полуплоскости, так что в каждой из них будет половина всех синих и половина всех красных (или, если N, нечетное в одной из половинок будет на 1 меньше тех и других): сначала произвольно разделяем поровну (при нечетном N - в одной части на 2 точки больше), потом вращаем прямую так, чтобы каждый раз она проскакивала одновременно по 2 точки (в разную сторону), тогда в пределах поворота на 180 градусов поймаем нужное разбиение.
К сожалению, у такого вращения не будет постоянного центра, вокруг которого точки можно было бы отсортировать по углу. Потому тут на каждом этапе возникает вопрос - как быстро находить очередную пару точек, в которые упрется прямая. Какое-нибудь r-tree или вроде того..
Первая идея — соединяем попарно красные с синими как получится, а потом, пока есть пересечения, меняем местами красные точки у любой пары пересекающихся отрезков. Эта замена убирает одно пересечение, но может создать еще несколько. Но каждая такая помена уменьшает общую длину отрезков (по неравенству треугольника), поэтому за конечное число шагов все пересечения будут убраны (ибо различных паросочетаний на этих точках конечное количество — n!).
Edit: мое решение совпало с авторским от составителей задачи. Вообще, если увлекаться математическими задачами, то быстро понимаешь, что полуинварианты или инварианты — одни из самых часто применяемых приемов.
Так-с, я придумал строго квадратичный алгоритм избавившись от построения полной оболочки.
Для начала выберем главное направление, такое чтобы проекции всех точек на него различались. Это не обязательно, но сильно упростит дальнейший алгоритм. Время — ϴ(N²)
Далее упорядочим все точки вдоль этого направления за ϴ(N log N).
Теперь основной цикл — для каждой группы точек (в начале она одна) посмотрим на цвета крайних точек:
- если они совпадают, то просканируем множество и разобьём его на две и более группы точек, после чего повторим этот шаг для каждой группы;
- если они различны, то попробуем построить часть выпуклой оболочки алгоритмом Джарвиса, выкидывая разноцветную пару как только она образовалась (построение заканчивается как только мы выкинули крайнюю точку)
Теперь оценим эти операции по времени.
Первая операция занимает O(N) времени, и сделать её придётся никак не больше O(N) раз.
При второй операции каждый шаг алгоритма Джарвиса занимает O(N) времени, и таких шагов придётся сделать ровно N/2.
Итоговое время ϴ(N²) + ϴ(N log N) + O(N)² + O(N)² = ϴ(N²).
При второй операции каждый шаг алгоритма Джарвиса занимает O(N) времени, и таких шагов придётся сделать ровно N/2.
Но ведь для джарвиса надо точки по углу отсортировать относительно крайней нижней. А если она будет выкинута? Плюс после разбиения придется хотя бы в одной половине сортировать заново, ведь точка-то центр одна, в обеих половинах ее быть не может.
Это для алгоритма Грехема сортировка нужна, Джарвис работает без предварительной сортировки
А ещё алгоритм Джарвиса жадный, чем я тоже пользуюсь в этом решении.
Перепутал. Но того вообще не понятно. Этот алгоритм за O(N) добовляет в оболочку ровно одну точку. Допустим, эта точка того же цвета, что и все остальные. Что дальше? Это еще не крайняя точка, мы не можем вот тут сразу взять и разбить точки на 2 половины, надо дальше достраивать оболочку.
Ну и достраиваем ее, в режиме стека: как только увидели точку другого цвета - выкинули две точки.
Так, я тут осознал что мы можем дойти до другого края так и не выкинув первую точку. В таком случае этот фрагмент оболочки надо сохранять во время "нарезки" чтобы не строить повторно. Поскольку режем мы всегда в одном направлении - сохранить кусок оболочки должно быть несложно.
Ну и достраиваем ее, в режиме стека: как только увидели точку другого цвета — выкинули две точки.
Ну так это будет O(N^2) до каждого разбиения пополам, если в оболочке все точки одного цвета. А после разбиения придется вообще с 0 эту оболочку строить. В итоге — O(N^3)
Про строить с 0 я уже дописал выше.
Каждая точка будет добавлена в оболочку один раз, плюс одна точка будет добавлена повторно на каждый разрез. Итого — шаг алгоритма Джарвиса будет выполнен 2O(N) раз, что даёт суммарное время потраченное на этот алгоритм O(N²).
Действительно, вы придумали алгоритм за O(n^2). Поздравляю. Но ваше объяснение сложновато понять. Я бы сформулировал так: поддерживаем нижнюю "половину" выпуклой оболочки — ломаная такая, что все остальные точки выше ее (и она выпуклая). Если концы одинакового цвета, то находим, где можно разбить на 2 множества вертикальной прямой. Иначае откусываем две крайние точки слева или справа. Потом алгоритмом заворачивания подарка (возможно по или против часовой стрелки) дополняем отрезанный кусок новыми отрезками ломанной из точек над откусанным отрезком.
Ваше меткое наблюдение о том, что кажая точка будет включена в такю ломанную ровно один раз, плюс один раз на каждое откусывание придется посмотреть, а не закончилась ли ломанная (следующий отрезок пересекает вертикальную прямоую и идет обратно). Поэтому итераций зваорачивания за O(n) будет максимум n+n (по точкам и по разбиениям).
А рекурсивные разбиения суммарно тоже дадут O(n^2), ведь если выкинуть уже оценненную часть от заворачивания подарка, то внутри каждой функции мы выполняем O(n) операций.
Заметим, что если на границе получившегося многоугольника хотя бы две точки имеют разный цвет, то рядом найдутся две точки разных цветов.
Непонятно, что значит "рядом" и почему это так.
Рядом — это в порядке обхода по выпуклой оболочке. Если эти 2 точки соединить, то никакой отрезок не сможет пересечь этот новый, ведь он на границе выпуклой оболочки.
Можно доказать что такие 2 точки существуют, например, по индукции. Или неформально — если идти вдоль оболочки, то начинали мы с синего цвета, а потом где-то пройдем через красный. Значит, где-то мы сделали шаг с синего на красный. Иначе бы так и остались на синем цвете.
Здорово, что тут два совершенно разных конструктивных решения. Жалею, что я сразу полез проверять своё решение (буквально слово в слово с вашим) и увидел авторское, не поискав его сам.
Задача про красные и синие точки