Namioty 3D

Namiot rozpięty na masztach dość dobrze oddaje pojęcie otoczki wypukłej zbioru. Wydaje się, że formalne definicje są tu zbyteczne, wystarczą poglądowe przykłady. Wcześniej przeczytaj artykuł o tym samym problemie w wersji płaskiej: Namioty 2D.
 

 
Napis A = koduje 'szkielet' namiotu nad prostokątem 5×4, na obwodzie którego ustawione są maszty o podanych wysokościach, w równych odstępach, co 1.
Kiedy patrzymy z góry, maszty widoczne są jako punkty .
Poniżej można zobaczyć ten sam szkielet w perspektywie. Można też zbadać inne szkielety.
 

Jasne jest, że namiot N_A rozpięty na szkielecie A = wygląda jak domek o dwuspadowym dachu. Ma on:

    -     2 + 1 + 4 = 7 ścian  (dach i podstawę też nazywamy ścianą),

    -     6 + 4 = 10 wierzchołków  (6 na dachu i 4 w podstawie),

    -     7 + 4 + 4 = 15 krawędzi  (7 na dachu, 4 w podstawie i 4 pionowe),

    -     6 istotnych masztów  (4 narożne i 2 w środkach krótszych boków; pozostałe są zbędne),

    -     objętość 110 (rozetnij na poziomie 4, potem górną część przepołów i złóż).

Jak badać namioty rozpięte na zadanych szkieletach?
Jak je sobie wyobrażać?

Po pierwsze: można na każdym z boków podstawy zbadać, które maszty są nieistotne tak, jak w wersji 2D. Pozostałe maszty będą istotne również w przypadku 3D.

Po drugie: oprócz 4 wierzchołków w narożach podstawy wierzchołkami namiotu będą jedynie górne wierzchołki istotnych masztów; nie przybędzie nowych wierzchołków.

Zatem wystarczy dalej zbadać, które z odcinków łączących istotne wierzchołki na dachu, są krawędziami namiotu. Nie podamy tu pełnego algorytmu. Zbadamy tylko pewne dość typowe przykłady.

Pomocna będzie następująca reguła:
Niech dwa odcinki łączące istotne wierzchołki dachu przechodzą nad pewnym punktem P podstawy. Wtedy:
    -   jeśli odcinki przecinają się nad P, to żaden z nich nie jest krawędzią namiotu,
    -   jeśli odcinek przechodzi pod drugim nad P, to nie jest krawędzią namiotu.

Rozważmy przykłady szkieletów: A = , B = , C = nad prostokątem 2×2.
Każdy z nich ma istotne tylko cztery maszty (narożne). Trzeba zatem rozstrzygnąć, które odcinki nad przekątnymi podstawy są krawędziami namiotu.

Powyższa reguła pozwala podać odpowiedzi, bo nietrudno sprawdzić, na jakiej wysokości przechodzą nad środkiem P podstawy.
 

Przeanalizujmy trudniejszy przykład szkieletu A = nad prostokątem 4×3 o wysokości 5.
Szkielety B = i C = mają takie same namioty: N_A = N_B = N_C .
Zbadamy zatem ten ostatni. Na dachu powstaje poziomy trójkąt na wysokości 5.
 
Jakie krawędzie należy jeszcze dorysować?
Oczywiście rozważamy jedynie odcinki łączące 6 istotnych wierzchołków na dachu.

Ustalmy najpierw, które odcinki nie będą krawędziami. Odcinki łączące lewy górny wierzchołek z wierzchołkami o wysokości 3 przechodzą pod odcinkiem 5-5, więc nie będą krawędziami.

Dalej można już odgadnąć odpowiedź i sprawdzić, że żaden inny odcinek nie jest krawędzią.
 
Zatem widać, że namiot N_A = N_B = N_C ma:
   -    4 + 1 + 4 = 9 ścian  (4 na dachu, 1 w podstawie i 4 boczne: 2 pięciokąty i 2 prostokąty),
   -    6 + 4 = 10 wierzchołków  (6 na dachu i 4 w podstawie),
   -    9 + 4 + 4 = 17 krawędzi  (9 na dachu, 4 w podstawie i 4 pionowe),
   -    objętość 54  (do prostopadłościanu 4×3×5 brakuje 3 ostrosłupów).

Spróbuj samodzielnie rozwiązać poniższe zadania (pochodzą z konkursu Koma'2015).
Umowa: maszty mają długości będące liczbami całkowitymi dodatnimi.
     

1.  Dla A = namiot N_A ma . . . ścian, . . . krawędzi, . . . wierzchołków i objętość . . . .
     

2.  Dla B = namiot N_B ma . . . ścian, . . . krawędzi, . . . wierzchołków i objętość . . . .
     

3.  Dla C = namiot N_C ma . . . ścian, . . . krawędzi i . . . wierzchołków.
     

4.  Największa objętość namiotu nad prostokątem 5×7 i wysokości 8 jest równa . . . .
     
     Najmniejsza objętość namiotu nad prostokątem 5×7 i wysokości 8 jest równa . . . .
     

5.  W wierzchołkach 36-kąta foremnego wystawione są prostopadle do tego wielokąta maszty o wysokościach: 1, 2, 3, ..., 36 (kolejno). Namiot rozpięty na tym szkielecie ma: . . . ścian i . . . krawędzi.
     

6.  W wierzchołkach 6-kąta foremnego o boku 1 wystawione są prostopadle do tego wielokąta maszty o wysokościach: 1, 2, 3, 4, 5, 6 (kolejno). Namiot rozpięty na tym szkielecie ma: . . . ścian i objętość równą . . . .
     

Na koniec zobaczmy bardziej skomplikowane namioty, których maszty stoją również we wnętrzu podstawy.