Минимальные сети на поверхностях многогранников (1103841), страница 16
Текст из файла (страница 16)
Âûáåðåì ëþáóþâåðøèíó íà ãðàíèöå M è, ïîëüçóÿñü ñëåäñòâèåì 4, ñîåäèíèì å¼ ãåîäåçè÷åñêèìè γi ñ êàæäîé èç âåðøèí ìíîãîãðàííèêà, ñîäåðæàùèõñÿ â M (åñëèòàêèå âåðøèíû åñòü). Òîãäà M \ ∪i γi ãåîäåçè÷åñêèé ìíîãîóãîëüíèê, íåñîäåðæàùèé âíóòðè ñåáÿ òî÷åê íåíóëåâîé êðèâèçíû. Òî÷íî òàê æå, êàêâ äîêàçàòåëüñòâå [1, Ãë.4,1,ëåììà 2], ðàçîáü¼ì M \ ∪i γi íà òðåóãîëüíèêèíåïåðåñåêàþùèìèñÿ äèàãîíàëÿìè (ò.å. ãåîäåçè÷åñêèìè ñ êîíöàìè â âåðøèíàõ ìíîãîóãîëüíèêà M \∪i γi , ïðè÷¼ì íà÷àëî è êîíåö äèàãîíàëè íå äîëæíûñîâïàäàòü). èòîãå ïîëó÷èì íåêîòîðóþ òðèàíãóëÿöèþ T âñåãî ìíîãîãðàííèêà P , êàæäûé òðåóãîëüíèê â êîòîðîé íå ñîäåðæèò âíóòðè ñåáÿ òî÷åê íåíóëåâîé êðèâèçíû, ò.å. èçîìåòðè÷åí ïëîñêîìó.
 ñèëó [1, Ãë. 4, 2, Ëåììà 1]äëÿ ëþáîãî µ > 0 ñóùåñòâóåò ν > 0 òàêîå, ÷òî íà ëþáîì ν -áëèçêîì êP ìíîãîãðàííèêå P 0 ñóùåñòâóåò òðèàíãóëÿöèÿ T 0 òîé æå êîìáèíàòîðíîéñòðóêòóðû, ÷òî è T , è òàêàÿ, ÷òî äëèíû ñîîòâåòñòâóþùèõ ð¼áåð äâóõ òðèàíãóëÿöèé îòëè÷àþòñÿ íå áîëåå ÷åì íà µ. Ñëîâà ¾òîé æå êîìáèíàòîðíîéñòðóêòóðû¿ îçíà÷àþò, ÷òî ñóùåñòâóåò ãîìåîìîðôèçì ψhom : P → P 0 , ïåðåâîäÿùèé âåðøèíû ìíîãîãðàííèêà P â ñîîòâåòñòâóþùèå âåðøèíû ìíîãîãðàííèêà P 0 , à òðèàíãóëÿöèþ T â òðèàíãóëÿöèþ T 0 . Ïóñòü ψ : P → P 0 êóñî÷íî-àôôèííûé ãîìåîìîðôèçì, êîòîðûé íà âåðøèíàõ òðèàíãóëÿöèè Tñîâïàäàåò ñ ψhom è êàæäûé òðåóãîëüíèê ∆ ∈ T àôôèííî îòîáðàæàåò íàψhom (∆).
Çäåñü ïîä àôôèííûì îòîáðàæåíèåì ∆ íà ψhom (∆) ìû ïîíèìàåì êîìïîçèöèþ (f 0 )−1 ◦ h ◦ f , ãäå f : ∆ → ∆0 ⊂ R2 è f 0 : ψhom (∆) →(ψhom (∆))0 ⊂ R2 èçîìåòðè÷íûå âëîæåíèÿ òðåóãîëüíèêîâ â ïëîñêîñòü,h : ∆0 → (ψhom (∆))0 àôôèííîå îòîáðàæåíèå ïëîñêèõ òðåóãîëüíèêîâ.Îòîáðàæåíèå ϕ : X → Y áóäåì íàçûâàòü ε-èçîìåòðèåé ïðîñòðàíñòâñ âíóòðåííåé ìåòðèêîé (X, ρX ) è (Y, ρY ), åñëè ϕ ãîìåîìîðôèçì è|ρY (ϕ(a), ϕ(b)) − ρX (a, b)| < ε äëÿ ëþáûõ a, b ∈ X .
Èç ñêàçàííîãî âûøå èñâîéñòâ àôôèííûõ îòîáðàæåíèé âûòåêàåò ëåììà.67Ëåììà 3.12. Äëÿ ëþáîãî ζ > 0 ñóùåñòâóåò ε > 0 òàêîå, ÷òî äëÿ ëþ-áîãî ìíîãîãðàííèêà P 0 , ε-áëèçêîãî ê P , ïîñòðîåííîå íàìè îòîáðàæåíèåψ : P → P 0 ÿâëÿåòñÿ ζ -èçîìåòðèåé.Ðàññìîòðèì äâîéñòâåííûé ãðàô D∗ ðàçâ¼ðòêè D (ò.å. àáñòðàêòíûéãðàô, ìíîæåñòâî âåðøèí êîòîðîãî ìíîãîóãîëüíèêè ðàçâ¼ðòêè, à ð¼áðàñîîòâåòñòâóþò ñêëååííûì ñòîðîíàì). Î÷åâèäíî, ÷òî ãðàô D∗ îòëè÷àåòñÿîò ãðàôà G ñåòè Γ ëèøü äîáàâëåíèåì âåðøèíû ñòåïåíè 2 âíóòðü êàæäîãîðåáðà (ýòà âåðøèíà ñòåïåíè 2 ñîîòâåòñòâóåò ïðÿìîóãîëüíèêó ðàçâ¼ðòêè).Íàéä¼ì â ãðàôå D∗ îñòîâíîå äåðåâî D0∗ è îïðåäåëèì íîâóþ ðàçâ¼ðòêó D0ñ òåì æå ìíîæåñòâîì ìíîãîóãîëüíèêîâ, ÷òî è â D, íî ñ ìåíüøèì íàáîðîì ïðàâèë ñêëåéêè îòîæäåñòâëÿþòñÿ òîëüêî ñòîðîíû, ñîîòâåòñòâóþùèå ðåáðó îñòîâíîãî äåðåâà D0∗ .
Íåôîðìàëüíî ãîâîðÿ, ìû ðàçðåçàåì ðàçâ¼ðòêó D ïî òåì ð¼áðàì, êîòîðûì â äâîéñòâåííîì ãðàôå ñîîòâåòñòâóþòð¼áðà, íå âõîäÿùèå â D0∗ .Äëÿ ìíîãîãðàííèêà P 0 ∈ P(k1 , . . . , kn ), ε-áëèçêîãî ê P (ìàëîå ε ìûîïðåäåëèì ïîçæå), ïîñòðîèì ψ . Ïîäìíîæåñòâî ψ(Bδ (Γ)) ìíîãîãðàííèêàP 0 , âìåñòå ñ ïåðåíåñ¼ííûì ñ D ñ ïîìîùüþ ψ ðàçáèåíèåì íà òðåóãîëüíèêèè ÷åòûð¼õóãîëüíèêè, ïðåäñòàâëÿåò ñîáîé ðàçâ¼ðòêó, êîòîðóþ ìû îáîçíà÷èì ÷åðåç D0 .  äâîéñòâåííîì ãðàôå ðàçâ¼ðòêè D0 ðàññìîòðèì ñîîòâåòñòâóþùåå îñòîâíîå äåðåâî (D00 )∗ = ψ ∗ (D0∗ ) (çäåñü ÷åðåç ψ ∗ : D∗ → (D0 )∗îáîçíà÷åí èçîìîðôèçì äâîéñòâåííûõ ãðàôîâ, èíäóöèðîâàííûé ãîìåîìîðôèçìîì ψ ) è îïðåäåëèì ðàçâ¼ðòêó D00 ñ òåì æå íàáîðîì ìíîãîóãîëüíèêîâ, ÷òî è D0 , è ïðàâèëàìè ñêëåéêè, çàäàííûìè ãðàôîì (D00 )∗ .
ßñíî, ÷òîðàçâ¼ðòêè D0 è D00 èçîìåòðè÷íû äèñêàì ñ ìíîãîãðàííûìè ìåòðèêàìè íóëåâîé êðèâèçíû. Ãðàíèöû ýòèõ äèñêîâ áóäåì îáîçíà÷àòü ÷åðåç ∂D0 , ∂D00 .Îòîáðàæåíèå ψ èíäóöèðóåò îòîáðàæåíèå ψi : Mi → Mi0 íà êàæäîì èç ìíîãîóãîëüíèêîâ Mi , ñîñòàâëÿþùèõ ðàçâ¼ðòêó D, à çíà÷èò è íà êàæäîì èçìíîãîóãîëüíèêîâ, ñîñòàâëÿþùèõ D0 . Îáúåäèíåíèå âñåõ ψi äà¼ò îòîáðàæåíèå ψ0 : D0 → D00 . Òàêèì îáðàçîì, ψ åñòü ôàêòîð-îòîáðàæåíèå îòîáðàæåíèÿ ψ0 ïî îòîæäåñòâëåíèþ ñòîðîí ðàçâ¼ðòêè D0 , ïðåâðàùàþùåìó D0 â D.ßñíî, ÷òî ψ0 ÿâëÿåòñÿ ε-èçîìåòðèåé ïðè âñåõ ε, ïðè êîòîðûõ ψ ÿâëÿåòñÿε-èçîìåòðèåé.Îáðàçû òî÷åê ñåòè Γ íà ðàçâ¼ðòêå D0 îáðàçóþò ñåòü, êîòîðóþ ìûîáîçíà÷èì ÷åðåç Γ0 . Íåôîðìàëüíî ãîâîðÿ, ñåòü Γ0 ïîëó÷àåòñÿ èç ñåòè Γ âðåçóëüòàòå ðàçðûâà íåêîòîðûõ å¼ ð¼áåð ïðè ðàçðåçå ðàçâ¼ðòêè D ïî ñòîðîíàì, íå ëåæàùèì â D0∗ .Ëîêàëüíî ìèíèìàëüíûì äåðåâîì áóäåì íàçûâàòü ñåòü, òèï êîòîðîé äåðåâî, âñå âåðøèíû êîòîðîãî èìåþò ñòåïåíü 1 è 3, ð¼áðà ãåîäåçè÷åñêèå, à óãëû ìåæäó ñìåæíûìè ð¼áðàìè ðàâíû 120◦ .
Ìíîæåñòâî âèñÿ÷èõâåðøèí ëîêàëüíî ìèíèìàëüíîãî äåðåâà H áóäåì íàçûâàòü åãî ãðàíèöåé èîáîçíà÷àòü ÷åðåç ∂H . ßñíî, ÷òî ñåòü Γ0 ëîêàëüíî ìèíèìàëüíîå äåðåâî68(ïîñêîëüêó D0∗ äåðåâî), ïðè÷¼ì ∂Γ0 ⊂ ∂D0 .Íàøà öåëü íàðèñîâàòü íà D00 ëîêàëüíî ìèíèìàëüíîå äåðåâî ñ ãðàíèöåé ψ0 (∂Γ0 ) è òîãî æå òèïà, ÷òî è Γ0 , êîòîðîå ïðè ïåðåõîäå îò D00 îáðàòíî ê D0 ïðåâðàùàëîñü áû â ìèíèìàëüíóþ ñåòü íà D0 . Íà ïëîñêîñòè ëîêàëüíî ìèíèìàëüíîå äåðåâî äàííîãî òèïà ñ äàííîé ãðàíèöåé ìîæåò áûòüïîñòðîåíî ñ ïîìîùüþ àëãîðèòìà Ìåëçàêà [32], àíàëîã êîòîðîãî äëÿ äèñêîâ ñ ìíîãîãðàííîé ìåòðèêîé, èìåþùèõ ðàçâ¼ðòêó òèïà D, è çàêëþ÷¼í âäîêàçàòåëüñòâå ñëåäóþùåé ëåììû.
Ñàìà ëåììà 3.13 ïðåäñòàâëÿåò ñîáîéîáîáùåíèå íà íàø ñëó÷àé ñëåäñòâèÿ èç àëãîðèòìà Ìåëçàêà î íåïðåðûâíîéçàâèñèìîñòè ëîêàëüíî ìèíèìàëüíîãî äåðåâà äàííîãî òèïà íà ïëîñêîñòè îòñâîåé ãðàíèöû [6, Ïðåäë.5.2].Ëåììà 3.13. Ïóñòü A ãîìåîìîðôíàÿ äèñêó ðàçâ¼ðòêà, ñîñòîÿùàÿ èçíåêâàäðàòíûõ ïðÿìîóãîëüíèêîâ øèðèíû 2δ è ïðàâèëüíûõ òðåóãîëüíèêîâñî ñòîðîíîé 2δ , ñêëååíûõ ïî íåêîòîðûì ñòîðîíàì äëèíû 2δ ;H ëîêàëüíî ìèíèìàëüíîå äåðåâî íà A ñ ãðàíèöåé ∂H ⊂ ∂A, ïðè÷¼ìïåðåñå÷åíèå ëþáîãî ïðÿìîóãîëüíèêà ðàçâ¼ðòêè ñ ñåòüþ H ðàâíî ñðåäíåéëèíèè ýòîãî ïðÿìîóãîëüíèêà, ñîåäèíÿþùåé ñòîðîíû äëèíû 2δ , à ïåðåñå÷åíèå ëþáîãî òðåóãîëüíèêà ðàçâ¼ðòêè ñ ñåòüþ H ñîñòîèò èç òð¼õ ïåðïåíäèêóëÿðîâ, îïóùåííûõ èç öåíòðà òðåóãîëüíèêà íà åãî ñòîðîíû;T òðèàíãóëÿöèÿ ðàçâ¼ðòêè A, ïîëó÷åííàÿ â ðåçóëüòàòå ðàçáèåíèÿêàæäîãî ïðÿìîóãîëüíèêà íà äâà òðåóãîëüíèêà ëþáîé èç äâóõ åãî äèàíãîíàëåé.Òîãäà äëÿ ëþáîãî λ > 0 ñóùåñòâóåò ζ > 0 òàêîå, ÷òî äëÿ ëþáîé ζ èçîìåòðèè ψζ : A → A0 , àôôèííîé íà òðåóãîëüíèêàõ èç T , ñóùåñòâóåòλ-èçîìåòðèÿ ψλ : A → A0 òàêàÿ, ÷òî ψλ |∂A = ψζ |∂A è H 0 = ψλ (H) ëîêàëüíî ìèíèìàëüíîå äåðåâî.Äîêàçàòåëüñòâî ëåììû ïðîâåä¼ì èíäóêöèåé ïî ÷èñëó ãðàíè÷íûõ(ò.å., íàïîìíèì, âèñÿ÷èõ) âåðøèí ñåòè H .
Áàçó èíäóêöèè ïðîâåðèì äëÿ |∂H| = 2.  ýòîìñëó÷àå äåðåâî H ñîñòîèò ëèøü èç îäíîãî ðåáðàãåîäåçè÷åñêîé γ , à ðàçâ¼ðòêà A ñîñòîèò èç íåñêîëüêèõ ïðÿìîóãîëüíèêîâ îäèíàêîâîé øèðèíû, ñêëååíûõ ïîñëåäîâàòåëüíî, è èçîìåòðè÷íà ïëîñêîìóïðÿìîóãîëüíèêó ñî ñðåäíåé ëèíèåé γ . ßñíî, ÷òîïðè ìàëîì ζ ðàçâ¼ðòêà A0 = ψζ (A) èçîìåòðè÷íà ïëîñêîìó ìíîãîóãîëüíèêó, ñêëååííîìó èç ïëîñêèõ ÷åòûð¼õóãîëüíèêîâ, áëèçêèõ ê ïðÿìîóãîëüíèêàì ðàçâ¼ðòêè A, è ïðè ìàëîì ζ îòðåçîê γ 0 , ñîåäèíÿþùèé ψζ -îáðàçû êîíöîâ ãåîäåçè÷åñêîé γ , ñîäåð- Ðèñ.
3.16: Áàçà: A è A0 .æèòñÿ âíóòðè ýòîãî ìíîãîóãîëüíèêà è äåëèò åãî íà äâà ìíîãîóãîëüíèêà.69Òðèàíãóëèðóåì êàæäûé èç ýòèõ äâóõ ìíîãîóãîëüíèêîâ-÷àñòåé íåïåðåñåêàþùèìèñÿ äèàãîíàëÿìè è ñäåëàåì êîìáèíàòîðíî òàêèå æå òðèàíãóëÿöèèìíîãîóãîëüíèêîâ A \ γ (ñ âåðøèíàìè â ψζ−1 -îáðàçàõ âåðøèí òðèàíãóëÿöèé ìíîãîóãîëüíèêîâ A0 \ γ 0 ). Îïðåäåëèì êóñî÷íî àôôèííîå îòîáðàæåíèåψλ : A → A0 , ñîâïàäàþùåå ñ ψζ íà âåðøèíàõ òðèàíãóëÿöèè è àôôèííîîòîáðàæàþùåå êàæäûé òðåóãîëüíèê òðèàíãóëÿöèè íà A â òðåóãîëüíèêòðèàíãóëÿöèè íà A0 . ßñíî, ÷òî ïðè äîñòàòî÷íî ìàëîì ζ îòîáðàæåíèå ψλáóäåò òðåáóåìîé λ-èçîìåòðèåé.Øàã èíäóêöèè: ïóñòü ëåììà äîêàçàíà äëÿ ñåòåé ñ k ãðàíè÷íûìè âåðøèíàìè,ðàññìîòðèì ñåòü H ñ |∂H| = k + 1. Íàéä¼ìâ ñåòè H ïàðó âèñÿ÷èõ âåðøèí, èìåþùèõîáùóþ ñìåæíóþ âåðøèíó, è îáîçíà÷èì èõñîîòâåòñòâåííî p, q , v , à ÷åðåç u îáîçíà÷èìòðåòüþ âåðøèíó, ñìåæíóþ ñ âåðøèíîé v .Îáîçíà÷èì ÷åðåç A1 îáúåäèíåíèå âñåõ ìíîãîóãîëüíèêîâ ðàçâ¼ðòêè A, ïåðåñåêàþùèõñÿñ ð¼áðàìè pv, qv, vu, è ñäåëàåì èçîìåòðè÷íîå âëîæåíèå A1 â ïëîñêîñòü, ñì.
ðèñ. 3.17Ðèñ. 3.17: Îò A ê Ak .(âëîæåíèå ñóùåñòâóåò, ïîñêîëüêó òðè ïðÿìîóãîëüíèêà, ïîñòðîåííûå íà ñòîðîíàõ ïðàâèëüíîãî òðåóãîëüíèêà, íå ìîãóò ïåðåêðûâàòüñÿ). Íà ïëîñêîñòè ïîñòðîèì ïðàâèëüíûé òðåóãîëüíèê ñîñíîâàíèåì pq è òðåòüåé âåðøèíîé s, ëåæàùåé ïî äðóãóþ ñòîðîíó îò ïðÿìîé pq , ÷åì òî÷êà v .
Ñîãëàñíî èçâåñòíîìó ôàêòó ïëàíèìåòðèè (èñïîëüçóþùåìóñÿ â êëàññè÷åñêîì àëãîðèòìå Ìåëçàêà), òî÷êà v ëåæèò íà ïåðåñå÷åíèè îòðåçêà us è ìåíüøåé äóãè pq îêðóæíîñòè, îïèñàííîé îêîëî 4pqs.Ïóñòü ∆(v) = xyz òðåóãîëüíèê ðàçâ¼ðòêè A, ñîäåðæàùèé âåðøèíó v ,ïðè÷¼ì xy åãî îñíîâàíèå, ïåðåñåêàþùåå ðåáðî uv , à M ìíîãîóãîëüíèê ðàçâ¼ðòêè, ïðèêëååíûé ê ∆(v) ïî ñòîðîíå xy . Óäàëèì èç ðàçâ¼ðòêè Aâñå ìíîãîóãîëüíèêè, ïåðåñåêàþùèå ð¼áðà pv, vq è äîáàâèì ïëîñêèé ïðÿìîóãîëüíèê abyx, â êîòîðîì s ñåðåäèíà ñòîðîíû ab, ïðèêëååííûé ïîîòðåçêó xy ê ìíîãîóãîëüíèêó M òàê, êàê ýòî ðåàëèçîâàíî íà ïëîñêîñòè.Íîâóþ ðàçâ¼ðòêó îáîçíà÷èì ÷åðåç Ak è ðàññìîòðèì íà íåé ñåòü, ïåðåñå÷åíèå êîòîðîé ñî âñåìè ¾ñòàðûìè¿ ìíîãîóãîëüíèêàìè òàêîå æå, êàê ó ñåòèH , à ïåðåñå÷åíèå ñ íîâûì ïðÿìîóãîëüíèêîì ðàâíî åãî ñðåäíåé ëèíèè. Òåìñàìûì èç ñåòè H óäàëåíû ð¼áðà pv, vq , à ðåáðî uv çàìåíåíî íà us.
Ïîëó÷èâøóþñÿ ñåòü íà ðàçâ¼ðòêå Ak îáîçíà÷èì ÷åðåç Hk . ßñíî, ÷òî ðàçâ¼ðòêàAk è ñåòü Hk óäîâëåòâîðÿþò óñëîâèÿì ëåììû è, áîëåå òîãî, óòâåðæäåíèåëåììû äëÿ íèõ âåðíî ïî ïðåäïîëîæåíèþ èíäóêöèè.Ïóñòü ψζ : A → A0 ζ -èçîìåòðèÿ ðàçâ¼ðòîê (äëÿ íåêîòîðîãî ζ , êîòîðîå ìû îïðåäåëèì íèæå), àôôèííàÿ íà òðåóãîëüíèêàõ èç T , ðàññìîòðèì70A01 = ψζ (A1 ) îáðàç òîé ÷àñòè ðàçâ¼ðòêè A, êîòîðóþ ìû ðàçâîðà÷èâàëè íà ïëîñêîñòü âûøå, è ñäåëàåì èçîìåòðè÷íîå âëîæåíèå A01 â ïëîñêîñòü.Äëÿ òî÷åê p0 = ψζ (p), q 0 = ψζ (q) ñòðîèì íà ïëîñêîñòè ïðàâèëüíûé òðåóãîëüíèê p0 q 0 s0 è ïàðàëëåëîãðàìì a0 b0 y 0 x0 ñ îñíîâàíèåì x0 y 0 , äëÿ êîòîðîãîs0 ñåðåäèíà ñòîðîíû a0 b0 . Óäàëÿåì èç A0 ìíîãîóãîëüíèêè, ñîîòâåòñòâóþùèå óäàë¼ííûì èç A, è äîáàâëÿåì ïàðàëëåëîãðàìì a0 b0 y 0 x0 , ïðèêëååíûéïî x0 y 0 ; íîâóþ ðàçâ¼òêó îáîçíà÷àåì ÷åðåç A0k . Îïðåäåëÿåì îòîáðàæåíèåψζ 0 : Ak → A0k , ñîâïàäàþùåå ñ ψζ íà Ak ∩A, è àôôèííî îòîáðàæàþùåå ïðÿìîóãîëüíèê abyx íà ïàðàëëåëîãðàìì a0 b0 y 0 x0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
