Всем доброго времени суток! Вот, пришла идея одной задачи, когда пытался решить вот эту. Не знаю, возможно, моя задача будет тривиальной, но всё равно выложу для общего развития, так сказать. Вся суть заключается в следующем:

Есть $%n$% точек с координатами $%(x_i, y_i)$%, где $%i=\overline{1,n}$%. Доказать, что всех их можно соединить в замкнутую фигуру (ну или доказать обратное). Другими словами, можно ли соединить все точки таким образом, чтобы от каждой точки выходило два отрезка (к двум другим точкам на плоскости) и чтобы ни один из этих отрезков не пересекался с каким-либо другим?

Дополнение. Будем считать что точки не лежат на одной прямой

PS. Мне удалось доказать это, приведя возможный алгоритм построения такой замкнутой фигуры. Возможно, существует более формализованный способ?

PPS. Долго думал к месту ли будет метка дисмата, в конце концов решил оставить. Мало ли

задан 30 Май '12 19:47

изменен 31 Май '12 0:03

Интересный метод. Стоит, конечно, попробовать.

Я рассуждал немного иначе. Пусть есть $%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$%. Таким образом, получаем решение

(30 Май '12 22:06) Limit-Sun

Я не очень понял, что происходит, а можно словами? Откуда и куда действует $%f$% и что значит крайняя правая точка (функции) $%F_1$%?

(30 Май '12 22:32) Fedya

Если вкратце - выбираем точку с наименьшим $%x_i$%, а если таких несколько выбираем из них ту, которая "выше" остальных (с наибольшим $%y_i$%). Далее строим две кусочно-линейные функции по точкам (с ограниченной областью определения), ну или попросту графики таким образом, что область значений одного графика $%E(F_1)$% "выше" выбранной точки (по координате $%y_i$%), а область значений другого графика $%E(F_2)$% "не ниже". Потом просто соединяем полученные графики слева и справа. Надеюсь (хотя сомневаюсь) в этот раз я объяснил понятней. Через время выложу полный алгоритм.

(30 Май '12 23:04) Limit-Sun

Я перенесла коммент @Fedya в ответы, так что новые комментарии должны быть тоже там

(30 Май '12 23:48) DocentI

@Limit-Sun, а с графиками не может быть такой проблемы: если несколько точек имеют одну абсциссу и разные ординаты, то соединяя их, мы не получим график? (т.е. не будет существовать такой кусочно-линейной функции)

(31 Май '12 0:11) Fedya

@Fedya, одна абсцисса, разная ордината не проблема, в решении я просто соединял от большей ординаты к меньшей. Термин "кусочно-линейная функция" - это первое, что мне пришло в голову для описания данной ситуации, хотя, строго говоря, полученные графики кусочно-линейными функциями не являются

(31 Май '12 1:08) Limit-Sun
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

По-моему, доказательство построением алгоритма довольно формальный способ. Можно доказать по индукции.

База индукции: в $%\mathbb{R}^2$% любые две точки можно соединить отрезком.
Индукционное предположение: Пусть можно соединить $%n-1$% точку
Шаг индукции: добавим ещё одну точку и найдём две ближайшие к ней точки, соединённые между собой отрезком.
Соединим новую точку отрезком с этими двумя, а старый отрезок удалим. Получим новую замкнутую фигуру. Единственное, в чём надо убедиться: не возникает ли самопересечений. Но даже если возникают, такой граф можно уложить в плоскость

ссылка

отвечен 30 Май '12 21:32

изменен 31 Май '12 0:10

@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
10|600 символов нужно символов осталось
2

Ладно, теперь мой алгоритм. Сначала выберем $%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$%. Поучим примерно такие графики:

alt text

Осталось только соединить крайние левые и крайние правые точки полученных графиков:

alt text

Дополнение. Но здесь есть один косяк (последний шаг не всегда так уж и гладко проходит), потом додумаю как исправить, не отклоняясь слишком сильно от алгоритма

PS. Никак не могу справиться с редактором формул =(

ссылка

отвечен 31 Май '12 0:42

изменен 31 Май '12 1:39

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,313
×845

задан
30 Май '12 19:47

показан
1496 раз

обновлен
31 Май '12 1:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru