Планаризация гранёной фигуры

[kray-zemli.livejournal.com]

Задали на собеседовании задачку. Контора занимается написанием САПР.

Есть 3D-фигура, содержащая N граней, которую предполагается развернуть на плоскость. Вопрос: какое число сгибов получится?

Название всей этой теории не знаю, поэтому гугл спросить не умею.

Для простых случаев число сгибов получается N-1. Каковы исключения из этого правила? И вообще, как эта область математики называется?

UPD: В комментах отсутствие исключений (для односвязных фигур) из правила N-1 доказывается через теорию графов.

Comments

[apashenko.livejournal.com]

Теория графов (http://ru.wikipedia.org/wiki/%D2%E5%EE%F0%E8%FF_%E3%F0%E0%F4%EE%E2).

[aterentiev.livejournal.com]

Если разворачивать с сохранением "полосочек для склеивания" (как кубики в детстве из бумаги клеили) - то N сгибов и останется.
Если нет и резать по грани - эта грань вычитается.

У меня есть подозрение, что универсального ответа на этот вопрос нет, просто смотрели, как человек подходит к аналитике. Что-то вроде известных гуглевских задач "сколько шариков для гольфа войдет в школьный автобус" и "сколько настройщиков пианино в мире".

[ohshitnotuagain.livejournal.com]

а человек такой "секундочку!" и в ЖЖ полез :)

[krazzzer.livejournal.com]

Вообще в 3D это называется mapping.

Но вам, похоже, нужно без искажения формы граней раскладывать.
Лидер такой раскладки - софтина "Prepakura Designer"

С точки зрения программирования не знаю, но может мой коммент поможет найти.

[pyka-npu3paka.livejournal.com]

http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D0%B3%D1%80%D0%B0%D0%BD%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2

[pyka-npu3paka.livejournal.com]

и ее обобщение
http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.AD.D0.B9.D0.BB.D0.B5.D1.80.D0.B0

[alex-djk1.livejournal.com]

Имхо - строим граф связей между гранями (связь это ребро), а потом по нему остовной граф.

[kray-zemli.livejournal.com]

Любое остовное дерево в графе с n вершинами содержит ровно n-1 ребро.

Спасибо! То что нужно!