Соединить точки без пересечений. Графы.

← →
O'ShinW © (2013-02-13 10:32) [0]

Задача соединить на плоскости точки, каждую с каждой, без пересечений.
4 точки - соединяются.
5 точек - нет. Но если очень хочется, то можно.
Дублируем одну из точек, и соединяем, как будто так и надо.
http://www.fotolink.su/v.php?id=50f38a8d93e277ec5a324b54c6a65d85

6, 7 точек
http://www.fotolink.su/v.php?id=c51925384dfe235c8356fb446ad52405
каждый раз приходится добавить/дублировать 1 точку.

В общем случае, при таком подходе, можно связать все точки со всеми, без пересечений. При неограниченной возможности дублирования.

Вопрос. Есть ли какая стратегия расположения точек, чтобы свести дублирование(приоритетно) и сумму длин(второстепенно) всех соединительных линий к минимуму?

← →
KilkennyCat © (2013-02-13 13:06) [1]

http://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D1%81%D1%81%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D0%B5%D1%87%D0%B0%D1%82%D0%BD%D1%8B%D1%85_%D0%BF%D0%BB%D0%B0%D1%82

← →
Inovet © (2013-02-15 13:00) [2]

> [0] O"ShinW © (13.02.13 10:32)
> на плоскости

Добавь измерения

← →
O'ShinW © (2013-02-15 13:05) [3]

> Добавь измерения

думал..
В 3х вообще легко. Надо что-то посмотреть из библиотек

концентрические окружности, соединённые прямой (и доказать, что каждая окружность является внешней границей точки :)

Соединить точки без пересечений. Графы. Найти похожие ветки