Привет, Хабр!
Недавно друзья задали мне задачу по дискретной математике. Задача так сильно понравилась, что я решил поделиться ей с широким кругом, а также рассказать свое решение и предложенное авторами задачи.
Текст задачи
Дана плоскость. На ней расположены n красных и n синих точек, причем никакие три точки не лежат на одной прямой. Докажите, что всегда можно соединить точки попарно непересекающимися отрезками так, что каждая красная точка соединена отрезком с синей и каждая синяя точка соединена отрезком с красной.
Предлагаю не переходить к разбору сразу, а остановиться и подумать. Ниже дана подсказка для самоконтроля, что условие правильно понято.
Подсказка для самоконтроля
Очевидно, что отрезков должно быть ровно n штук.
В самом деле, у нас n красных точек. На каждую красную точку требуется хотя бы один отрезок, поэтому отрезков должно быть хотя бы n.
При этом никакую точку не получится соединить больше чем с одной другой, т.к. в противном случае точка будет лежать на двух различных отрезках, а значит, технически будет являться точкой их пересечения, что запрещено. Следовательно, всего n отрезков.
Мое решение
Докажем по индукции. База - пустое множество точек. Идея перехода в том, чтобы свести задачу размера n к задачам размера меньше n.
Рассмотрим границу выпуклой оболочки множества всех точек (представьте, что мы натянули канцелярскую резинку на точки так, что они оказались внутри, часть точек попали на границу). Заметим, что получился многоугольник, в углах которого лежат точки. Причем точки могут лежать только в его углах, т.к. по условию никакие три точки не лежат на одной прямой.
Заметим, что если на границе получившегося многоугольника хотя бы две точки имеют разный цвет, то рядом найдутся две точки разных цветов. Найдем две такие точки, соединим отрезком. Теперь все остальные точки оказались в одной из полуплоскостей относительно прямой, на которой лежит наш отрезок, а значит никакие другие возможные отрезки с ним не пересекутся, т.е. можно "удалить" данную пару точек и перейти к задаче размера n - 1.
Так можно делать до тех пор, пока на границе выпуклой оболочки лежат хотя бы две точки разных цветов. Отдельно рассмотрим случай, когда все точки на границе имеют один цвет.
Не умаляя общности предположим, что все точки на границе оказались синими. Поскольку множество точек конечно, конечно и множество прямых, на которых лежат хотя бы две точки. Следовательно конечно и множество углов наклонов этих прямых. А значит, можно выбрать новый угол наклона, такой что никакие две точки не лежат на прямой с таким углом. Построим прямую с этим самым углом и начнем ее двигать (для определенности - слева на право). Тогда все точки сначала окажутся в правой полуплоскости относительно прямой, затем их количество будет изменяться по мере пересечения прямой с точками, и в конце - все точки окажутся слева.
Заметим, что самая левая и самая правя точки принадлежат границе выпуклой оболочки, а значит - они одного цвета!
Будем считать количество синих и красных точек слева от прямой: red_cnt(x) и blue_cnt(x). Изначально red_cnt(x) = blue_cnt(x) = 0. Затем прямая пересекает первую синюю точку и тогда red_cnt(x) = 0, blue_cnt(x) = 1. По мере продвижения прямой вправо эти числа растут (каждый раз одно из чисел увеличивается на 1). В конце будет добавлена последняя синяя точка и числа достигнут n (red_cnt(x) = blue_cnt(x) = n). Это значит, что прежде чем последняя синяя точка была добавлена значения были red_cnt(x) = n, blue_cnt(x) = n - 1. Т.е. мы имеем две функции, причем blue_cnt начала расти раньше, но достигла n позже чем red_cnt. А значит - эти функции принимают одинаковое значение где-то между началом левой и правой точкой: red_cnt(x) = blue_cnt(x). Иными словами, существует прямая, которая делит плоскость на две непустые полуплоскости, в каждой из которых равное количество синих и красных точек! А значит, мы свели задачу размера n к двум задачам меньшего размера. Ч.т.д.
Решение авторов задачи
Построим n отрезков, концы которых соединяют точки разных цветов (не обязательно без пересечений). Строить можно так: пока есть точки не соединенные отрезком, будем брать пару "свободных" точек и соединять их.
Теперь рассмотрим любую пару отрезков, которые имеют пересечение (см. рисунок). Удалим два отрезка с пересечением и построим два новых отрезка без пересечений. Заметим, что в силу неравенства треугольника, каждый раз выполняя такое действие, мы уменьшаем суммарную длину всех имеющихся отрезков. Поскольку количество способов соединить отрезки конечно и каждый раз мы переходим от одного способа к другому, уменьшая суммарную длину, то данный процесс должен будет однажды остановиться. В этот момент у нас не окажется больше пересечений, следовательно мы всегда получим искомое построение. Ч.т.д.
Заключение
Особенность второго решения в том, что мы ввели некоторый числовой параметр, которым охарактеризовали построение и научились делать действия, приводящие к его уменьшению. Лично мне оно напомнило задачу с двадцатью картами из моего любимого фильма X+Y (см. отрывок на англ.), таким образом нашло отклик в моей душе. Однако, если бы я сразу подсмотрел его, то ни за что не придумал бы своего.
Благодарности
Спасибо авторам Ace Your Next Coding Interview, благодаря которым я узнал о данной задаче.
Также отдельное спасибо Виктору Крыштаповичу и Артему Грачеву, которые слушали мой поток сознания.
Комментарии (24)
GospodinKolhoznik
20.06.2023 05:36+1Мне кажется, что ситуацию, когда конец одного отрезка является началом другого, не принято называть пересечением отрезков. Разве отрезки, образующие стороны квадрата, пересекаются? Хотя это всё вопрос договорённости терминологии.
demitryy Автор
20.06.2023 05:36+1Для меня пересечение отрезков - это пересечение множеств их точек. Оно даже обозначается через тот же символ пересечения:
:)GospodinKolhoznik
20.06.2023 05:36+1Однако про касательную к окружности, имеющей с ней общую точку не говорят, что она пересекает окружность. А пересечение множества точек при этом не пусто.
Akina
20.06.2023 05:36+1Касание - это формально разновидность пересечения. Ведь в определении пересечения нет требования наличия не менее 2 общих точек, вроде как..
qw1
20.06.2023 05:36+1Для задачи это несущественно, потому что доказано существование более строгого решения, когда точки соединяются только попарно. Можно начать доказательство с фразы "докажем, что существует решение, где точки соединяются только попарно", и забыть про ваш случай.
cliver
20.06.2023 05:36+2YT видео по подобной задаче, если кому интересно
vvovas
20.06.2023 05:36Я не математик, поэтому вопрос может быть глупый, но переходя от диагоналей к сторонам мы не гарантируем, что из-за этого не появится новое пересечение. Допустим в описаном примере была бы точка внутри треугольника AXD, которая соединялась с другой точкой за пределами ABCD. Меняя AD, на AC мы создаем новое пересечение. Каким образом доказать, что череда таких новых пересечений когда-нибудь закончится?
Alexandroppolus
20.06.2023 05:36+3Каким образом доказать, что череда таких новых пересечений когда-нибудь закончится?
Каждый переход от диагоналей к сторонам уменьшает суммарную длину отрезков, т.е. это нельзя делать до бесконечности.
Naf2000
20.06.2023 05:36+2Строго говоря требуется не просто уменьшение, а уменьшение не меньше чем фиксированная величина. Иначе действительно можно очень долго уменьшать (бесконечно). Но в силу конечности множества точек, а значит и отрезков и разностей расстояния между ними - такая величина безусловно найдётся.
Alexandroppolus
20.06.2023 05:36+2Доказательство - это круто, но не менее интересен вопрос об оптимальном алгоритме такого соединения точек. Представленные решения будут явно медленнее O(N^2) в худшем случае.
farafonoff
20.06.2023 05:36Алгоритм с разбиением делается за n^2, и это легко показать.
Поиск выпуклой оболочки требует попарного вычисления полярных углов, это n^2, и сами углы можно запомнить (n^2 памяти). После удаления пары точек из выпуклой оболочки нет нужды пересчитывать все углы заново.
Если выпуклая оболочка состоит из точек одного цвета, то спроецируем наши точки на какую-то прямую, и зададим их порядок (прямую можно брать произвольную, в худшем случае на одну точку прямой спроецируются 2 точки множества, порядок для них можно выбрать произвольный).
Поскольку первая и последняя точки по условию одного цвета, найдется такая точка на нашей делящей прямой, слева и справа от которой одинаковое количество красных и синих точек. Проверить этот факт можно за n. Затем рекурсивно вызываем алгоритм для каждого подмножества, так как они гарантировано не пересекаются.
qw1
20.06.2023 05:36А если выпуклая оболочка состоит из точек разного цвета?
Удаляем соседние пары разного цвета и снова запускаем алгоритм поиска оболочки за N^2?farafonoff
20.06.2023 05:36Удалить одну точку из выпуклой оболочки можно за n - нужно пересчитать всего одно ребро.
mayorovp
20.06.2023 05:36Ну, если считать "в лоб", то получается O(N2 log N), что не сильно-то медленнее "квадрата".
qw1
20.06.2023 05:36В лоб — это соединить попарно любые точки разного цвета, а потом найти все пересечения отрезков (N^2), в пересекающихся парах поменять точки. Выполнить алгоритм заново с шага поиска пересечений. Как доказать, что число итераций не больше log N?
mayorovp
20.06.2023 05:36Делать-то надо как автор написал, это подсчёт я провёл "в лоб".
Выпуклая оболочка строится алгоритмом Грехема за N log N, построить её придётся не более N раз. Всё, время равно O(N2 log N)
fvariation
Или это дежавю или действительно в какой-то книжке или статье по SQL я видел задачу на эту тему. Типа есть n точек, то есть n записей в таблице - "X,Y, Цвет". Составить SQL запрос, который выдаст пары точек X,Y,X1,Y1 для которых выполняются условия задачи, ну или что-то в этом роде. Может кто-то прояснить?
demitryy Автор
На самом деле, особенностью конкретно этой задачи является геометрическая часть. Конкретно условия, что отрезки не пересекаются и никакие три точки не лежат на одной прямой. Данные условия сложно формализовать и описать в терминах SQL, поэтому я думаю, что это просто похожая задача.
Akina
Это неверно. Есть spatial datatype и целая пачка GIS-функций, которые позволяют хранить точки, комбинировать их в отрезки и проверять отрезки на пересечение. Скажем, та же ST_Crosses() проверяет, пересекаются ли две LINESTRING.
А проверка, что никакие три точки не лежат на одной прямой, в общем, и не требуется - формально мы имеем право считать, что условие корректно, и данных, не соответствующих условию, нет. Хотя и проверка - тоже не проблема. Хоть обычной пропорцией, хоть опять же через spatial-функции.
fvariation
Условия они и есть условия, к "терминам SQL" отношения не имеют. Это именно решение, которое нужно сделать в "SET" идеологии, что не просто как по мне, имеющему к айти очень косвенное отношение, тем более к SQL технологиям, хотя математику при Брежневе в институте изучал.
Пусть у нас k вариантов соединения n+n точек в отрезки, причем цвета точек краев отрезка разные.
Как я понимаю, запросом нужно получить таблицу всех отрезков для всех вариантов соединения, то есть - 4 столбца X1, Y1, X2, Y2 и пятый столбец - номер варианта соединения от 1 до k. Понятия не имею с чего начать, но наверное это будет рекурсия от 1 до k скорее всего с применением CTE (Common Table Expression) Когда такая таблица есть, то поверх неё просто нужен запрос найти номера таких вариантов соединения для которых не существует пары отрезков, которые пересекаются.
mayorovp
Условия-то как раз формализовать просто, проблема тут в том что это условие на множество всех строк а не на строку, то есть запрос надо делать не относительно таблицы точек, а относительно множества всех подмножеств строк этой таблицы.
Для таких запросов, во-первых, в SQL нет нормальных операторов, а во-вторых, нет алгоритмов оптимизации.
qw1
Ошибся стрелочкой, должен быть плюс.
fvariation
Это примерно то, что я написал, только другими словами.
Воистину нет, ибо никто и не обещал что такое решение оптимально, - просто задача, вряд ли имеющая прикладное значение. На входе - таблица, где запись - координаты X, Y точек и её цвет, 2*n точек, то есть записей.
Запросом получаете таблицу всех возможных вариантов соединений точек удовлетворяющих условиям. Каждая запись в этой таблице - номер варианта, четыре координаты двух точек (или, если хочется нормализации, - номера точек)
По этой таблице делаете запрос - найти номера таких вариантов соединения для которых не существует пары отрезков, которые пересекаются. SQL NOT EXISTS operator в этом контексте, как по мне, должен работать вполне оптимально. Имеет такая задача прикладное значение (в т.ч. специальное) или нет - пусть каждый решает для себя сам.