Многогранник Шёнхардта

Многогранник Шёнхардта — простейший невыпуклый многогранник, который нельзя триангулировать тетраэдрами без добавления новых вершин. Многогранник назван именем немецкого математика Эриха Шёнхардта, построившего его в 1928 году.

многогранник Шёнхардта
Многогранник Шёнхардта
Тип	невыпуклый многогранник
Свойства	Невыпуклый Не имеет внутренних диагоналей нетриангуляризуем
Комбинаторика
Элементы	12 рёбер 6 вершин
Грани	8 треугольников
Медиафайлы на Викискладе

Построение

Многогранник Шёнхардта можно построить с помощью двух конгруэнтных правильных треугольников на двух параллельных плоскостях, таких, что прямая, проведённая через середины треугольников, перпендикулярна плоскостям. Два треугольника должны быть повёрнуты относительно друг друга так, что они не являются ни параллельным переносом друг друга, ни поворотом на 180º.

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

Многогранник Шёнхардта можно образовать также удалением трёх тетраэдров из выпуклой оболочки. Каждый удаляемый тетраэдр является выпуклой оболочкой четырёх вершин двух треугольников, по два от каждого. Это удаление приводит заменой длинных соединяющих ребер тремя новыми рёбрами с вогнутыми двугранными углами, что даёт невыпуклый многогранник.

Описание

Многогранник Шёнхардта комбинаторно эквивалентен правильному октаэдру. То есть, его вершины, рёбра и грани можно взаимно однозначно сопоставить вершинам, рёбрам и граням правильного октаэдра. Но, в отличие от правильного октаэдра, три ребра имеют вогнутые двугранные углы и эти три ребра образуют совершенное паросочетание графа октаэдра. Этот факт существенен для доказательства отсутствия триангуляризации.

Шесть вершин многогранника Шёнхардта можно использовать для получения пятнадцати неупорядоченных пар вершин. Двенадцать из этих пятнадцати пар образуют рёбра многогранника — шесть являются рёбрами двух правильных треугольных граней, а шесть рёбер соединяют эти два треугольника. Оставшиеся три ребра образуют диагонали многогранника, но они лежат полностью вне многогранника.

Невозможность триангуляции

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

Приложения

Рупперт и Зайдель использовали многогранник Шёнхардта как основу доказательства NP-полноты проверки, что невыпуклый многогранник можно триангулизировать.

Вариации и обобщения

Скрученная квадратная антипризма

• Как показал Рамбо, существуют многогранники, комбинаторно эквивалентных антипризмам, подобные многограннику Шёнхардта — их нельзя триангулировать. Эти многогранники можно получить соединением правильных k-угольников в двух параллельных плоскостях, повёрнутых относительно друг друга таким образом, что k из 2k рёбер, соединяющих два k-угольника, имеют вогнутые двугранные углы.
• Икосаэдр Йенсена — другой многогранник, который не допускает триангуляции без дополнительных вершин.
• В 1948 году Бэйджмил построил многогранник, который также как и многогранник Шёнхардта не имеет внутренних диагоналей.
  • Тетраэдр и многогранник Часара не имеют диагоналей вообще — каждая пара вершин в этих многогранниках является ребром.
  • Остаётся неясным вопрос о существовании других многогранников (с границами в виде многообразия) без диагоналей, хотя существуют поверхности без диагоналей с любым числом вершин, большим пяти, но их границы не являются многообразиями.

См. также

• Задача о триангуляции многоугольника

Литература

• F. Bagemihl. On indecomposable polyhedra // American Mathematical Monthly. — Mathematical Association of America, 1948. — Т. 55, вып. 7. — С. 411—413. — doi:10.2307/2306130. — ..
• J. Rambau. Combinatorial and computational geometry. — Cambridge: Cambridge University Press, 2005. — С. 501—516.
• J. Ruppert, R. Seidel. On the difficulty of triangulating three-dimensional Nonconvex Polyhedra. — Discrete Comput. Geom.. — 1992. — Т. 7. — С. 227—253. — doi:10.1007/BF02187840. (недоступная ссылка)
• E. Erich Schönhardt. Über die Zerlegung von Dreieckspolyedern in Tetraeder // Math. Annalen. — 1928. — Т. 98. — С. 309—312. — doi:10.1007/BF01451597. (недоступная ссылка)
• Sándor Szabó. Polyhedra without diagonals // Periodica Mathematica Hungarica. — 1984. — Т. 15, вып. 1. — С. 41—49. — doi:10.1007/BF02109370.
• Sándor Szabó. Polyhedra without diagonals II // Periodica Mathematica Hungarica. — 2009. — Т. 58, вып. 2. — С. 181—187. — doi:10.1007/s10998-009-10181-x.
• Günter M. Ziegler. Discrete Differential Geometry / A. I. Bobenko, P. Schröder, J. M. Sullivan, G. M. Ziegler. — Springer-Verlag, 2008. — Vol. 38. — С. 191—213. — (Oberwolfach Seminars). — ISBN 978-3-7643-8620-7. — doi:10.1007/978-3-7643-8621-4_10.

Ссылки

• Three Untetrahedralizable Objects, D. Eppstein. Включает вращающуюся трёхмерную модель многогранника Шёнхардта.