Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Mr. Bean és a falfestés dinamittal

Berzsenyi Matektábor 2014
by

Viktor Jeges

on 13 April 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Mr. Bean és a falfestés dinamittal


olyan egyszerű sokszög, melynek minden belső szöge 90°-os vagy 270°-os
Definíció:
Pisze ortogonális sokszög
(majdnem ortogonális)
1. Minden éle "ortogonális", kivéve egyet ("dőlt él")
2. A dőlt él két szomszédos éle párhuzamos
3. Minden szöge
4. Az orrban nincs piercing: (nincs csúcs az orrban)
Minden pisze ortogonális sokszög felbontható konvex négyszögekre
Állítás:
Bizonyítás:
Teljes indukció!
1. n=4
2. tegyük fel, hogy k-nál kisebb n-ekre beláttuk
3. n=k-ra igaz?
Mr. Bean és a falfestés dinamittal
Általános sokszögek
Állítás: Minden sokszög háromszögekre bontható
Tegyük fel, hogy létezik csak konkáv belső szögekkel rendelkező n csúcsú sokszög.
A sík így két részre van osztva, ahol a külső síkrészt egy csak konvex szögekkel rendelkező poligon határolja.
Mivel konvexek a szögek, be lehet húzni külső átlókat.
Sokszögek fajtái
1973 Klee: a probléma felvetése
Chvátal – első eredmények és megoldás
Fisk – eddigi legelegánsabb megoldás
Az egész így körbehatárolható, és mivel a végén egy háromszög keletkezik, ahol a terület külső síkrész a szögek meg konvexek, ellentmondást találunk.
bontsuk háromszögekre
színezzük ki a csúcsokat
Válasszunk C pontot!
Pisze ortogonális?
Minden ortogonális sokszög felosztható konvex négyszögekre
Lemma:
Képtár probléma variációk
Őrök:
csúcsokban
oldalakon
a sokszög belsejében
További lehetőség: sétáló őrök
Ortogonális sokszögek
Kahn, Klawe, Kleitman
Minden egyszerű ortogonális sokszög felbontható belső átlókkal konvex négyzögekre
[n/4] őr elegendő n oldalú sokszögnél – néha szükséges
Újabb problémák
A teremben vannak „lyukak” (oszlopok)
Ellenőrzött őrök (minden őrt lát egy másik őr)
Michael, Pinciu
Hernández-Peñalver
Külső őrök (a képtárat kívülről örzik)
Az őrök csak bizonyos szögben látnak (nem forognak, nem látnak a hátuk mögé)
Három dimenzió (térben)
válasszunk ki egy háromszöget
indukció
A képtár problémája
Forrás
Legyen K<P és K<Z
Joseph O'Rourke: Art Gallery Theorems and Algorithms
http://www.ams.org/samplings/feature-column/fcarc-diagonals1
http://www.ams.org/samplings/feature-column/fcarc-gallery1
És a kép összeáll!
Tehát vegyünk egy pisze-ortogonális sokszöget
És konvex négyszögesítsük
S
z
í
n
e
z
é
s
1. lépés színezzünk ki egy
konvex négyszöget
2. lépés
folytassuk
3. lépés
és így tovább
És ahogy a főzős műsorokban mondják:
Hogy miért is kell ez?
zöld: 12db
sárga: 13db
piros: 14db
kék: 13db
És végre elhelyezhetjük az őröket!
Mikor kell ennyi?
-avagy lesz-e olyan helyzet amikor
szűkséges az n/4 őr
És itt mért nincs probléma?
Nézzük rajta is a már bemutatott lépéseket
1. ) Konvex négyszögesítés
2.) Színezés
3.) lépés őrök elhelyezése
Általánosan
1. Állítás
: Minden sokszögnek van belső átlója.
2. Állítás
: Minden sokszög háromszögekre bontható
A triangularizáció indukciója
duális gráf
Képtár probléma


11. C: Bottlik Judit, Zsakó Ágnes, Nagy Simon, Erdős Zoltán, Fónai Martin, Hornák Bence
11. B: Jeges Viktor, Szabó János

Készítette:
Köszönjük a segítséget:
Sztranyák Attila tanár úrnak
http://zeus.nyf.hu/~mattan/faliujsag/konvex.pdf
http://people.inf.elte.hu/lukovszki/Courses/07NWT/xnwt08.pdf
http://mathworld.wolfram.com/ArtGalleryTheorem.html
Ortogonális sokszögek
C pont 3 féle lehet
Új kitüremkedés->új őr
, tehát
Full transcript