|
Всем доброго времени суток! Вот, пришла идея одной задачи, когда пытался решить вот эту. Не знаю, возможно, моя задача будет тривиальной, но всё равно выложу для общего развития, так сказать. Вся суть заключается в следующем: Есть $%n$% точек с координатами $%(x_i, y_i)$%, где $%i=\overline{1,n}$%. Доказать, что всех их можно соединить в замкнутую фигуру (ну или доказать обратное). Другими словами, можно ли соединить все точки таким образом, чтобы от каждой точки выходило два отрезка (к двум другим точкам на плоскости) и чтобы ни один из этих отрезков не пересекался с каким-либо другим? Дополнение. Будем считать что точки не лежат на одной прямой PS. Мне удалось доказать это, приведя возможный алгоритм построения такой замкнутой фигуры. Возможно, существует более формализованный способ? PPS. Долго думал к месту ли будет метка дисмата, в конце концов решил оставить. Мало ли задан 30 Май '12 19:47 
Limit-Sun
показано 5 из 6
показать еще 1
|
|
По-моему, доказательство построением алгоритма довольно формальный способ. Можно доказать по индукции. База индукции: в $%\mathbb{R}^2$% любые две точки можно соединить отрезком. отвечен 30 Май '12 21:32 
Fedya @Fedya, извините, что вмешиваюсь, но Ваш комментарий достаточно развернутый и я превратила его в ответ. Если Вы недовольны - скажите.
(30 Май '12 23:47)
DocentI
Что такое "две ближайшие точки, соединенные отрезком"? Найти просто две ближайшие точки - можно, есть первая ближайшая и вторая ближайшая. Но вдруг они не соединены? А среди пар соединенных не очень понятно, какую выбрать. Если одна пара находится на расстояниях (1; 6) отновой точки, а другая - на расстояниях (2; 3) - то какая из них ближе? Может, как-то использовать выпуклую оболочку? Т.е. выбирать новую точку так, чтобы она лежала вне выпуклой оболочки всех остальных?
(30 Май '12 23:53)
DocentI
Минимум ищется среди пар соединённых, выбрать можно любую пару, здесь важно, что на каждом шаге добавляется одна вершина и одна сторона (две новых добавляются, одна удаляется). Правда тогда базу индукции нужно брать не две точки, а три. Конечно, будут самопересечения, но здесь я хочу полениться и сослать на теорему об укладке графов в плоскость (теорема Понтрягина-Куратовского). Если пытаться строить сразу без самопересечений, надо придумывать более хитрый алгоритм построения
(31 Май '12 0:01)
Fedya
Формально, можно так - ищем ближайшую точку, затем выбираем любую из двух точек, с которыми она соединена отрезками. Получим то, что нужно.
(31 Май '12 0:04)
Fedya
В принципе, идея верная
(31 Май '12 0:13)
Limit-Sun
|
|
Ладно, теперь мой алгоритм. Сначала выберем $%y_k$% следующим образом - $%y_k$% - координата точки, у которой координата по оси абсцисс ($%x_k$%) имеет минимальное значение. Если таких точек несколько выбираем ту, у которой $%y_i$% наибольшая. Далее, просто соединяем точки отрезками таким образом, что между соединяемыми точками минимальное расстояние по оси абсцисс, и для которых выполняется $%y_i\geq y_k$%. В том случае, если таких точек (на определённой итерации) несколько первоначально выбираем ту, у которой $%y_i$% наибольшая и далее соединяем последовательно отрезками с точками, координаты которых по оси ординат $%y_{i_1}$%, $%y_{i_2}$%... $%y_{i_k}$%, где $%y_{i_1}> y_{i_2}>...> y_{i_k}$% (при $% x_{i_1}=x_{i_2}=...= x_{i_k}$%). Продолжаем построение до тех пор, пока существует хотя бы одна точка, значение координаты $% x_i $% которой, больше значения координаты $%x_{i-1}$% - последней точки, которая соединена одним отрезком. После того, как соединим, таким образом, все доступные точки, проделаем, ту же процедуру, но теперь обязательное условие для присоединяемых точек будет $%y_i< y_k$%. Поучим примерно такие графики:
Осталось только соединить крайние левые и крайние правые точки полученных графиков:
Дополнение. Но здесь есть один косяк (последний шаг не всегда так уж и гладко проходит), потом додумаю как исправить, не отклоняясь слишком сильно от алгоритма PS. Никак не могу справиться с редактором формул =( отвечен 31 Май '12 0:42
Limit-Sun |
Интересный метод. Стоит, конечно, попробовать.
Я рассуждал немного иначе. Пусть есть $%f_{const}=y_k$%, где $%y_k$% из $%max_{y_i}(\{min_{x_j}(x_k,y_k)\})$%. После этого строим кусочно-линейные функции $%F_1$% и $%F_2$%, таким образом, что $%F_1>f_{const}$% и $%F_2\leq f_{const}$%. Далее соединяем крайнюю правую точку $%F_1$% с крайней правой $%F_2$% и крайнюю левую точку $%F_1$% с крайней левой $%F_2$%. Таким образом, получаем решение
Я не очень понял, что происходит, а можно словами? Откуда и куда действует $%f$% и что значит крайняя правая точка (функции) $%F_1$%?
Если вкратце - выбираем точку с наименьшим $%x_i$%, а если таких несколько выбираем из них ту, которая "выше" остальных (с наибольшим $%y_i$%). Далее строим две кусочно-линейные функции по точкам (с ограниченной областью определения), ну или попросту графики таким образом, что область значений одного графика $%E(F_1)$% "выше" выбранной точки (по координате $%y_i$%), а область значений другого графика $%E(F_2)$% "не ниже". Потом просто соединяем полученные графики слева и справа. Надеюсь (хотя сомневаюсь) в этот раз я объяснил понятней. Через время выложу полный алгоритм.
Я перенесла коммент @Fedya в ответы, так что новые комментарии должны быть тоже там
@Limit-Sun, а с графиками не может быть такой проблемы: если несколько точек имеют одну абсциссу и разные ординаты, то соединяя их, мы не получим график? (т.е. не будет существовать такой кусочно-линейной функции)
@Fedya, одна абсцисса, разная ордината не проблема, в решении я просто соединял от большей ординаты к меньшей. Термин "кусочно-линейная функция" - это первое, что мне пришло в голову для описания данной ситуации, хотя, строго говоря, полученные графики кусочно-линейными функциями не являются