Konvex sokszög beírt sokszögeinek extremális tulajdonságai
Az [1] tanulmány szerzői leírtak egy O(n^3) komplexitású algoritmust egy adott konvex n-szög köré írható maximális területű konvex sokszögek megkeresésére. Megmutatták, hogy az így kapott maximális területű sokszögek kombinatorikus tulajdonságait meghatározza egy olyan U-ból és N-ből álló sorozat, melyben az eredeti sokszög oldalaihoz rendre U-t vagy N-et rendelünk aszerint, hogy az oldal része-e az algoritmus által talált maximális területű köréírt sokszög egy oldalának, vagy sem. Ez alapján a szerzők azt is vizsgálták, hogy melyek azok az n-elemű, U-ból és N-ből álló sorozatok, melyek előállnak, mint egy alkalmas konvex n-szög köré írt valamely maximális területű konvex sokszöghöz rendelt sorozat.
Ez a dolgozat a fenti tanulmány folytatása. A dolgozat elsődleges célja egy adott konvex n-szögbe írható minimális területű vagy minimális kerületű sokszögek megtalálására alkalmas algoritmus kidolgozása, illetve az így kapott sokszögek kombinatorikus tulajdonságainak jellemzése. Belátjuk, hogy egy adott konvex n-szög egy minimális területű beírt sokszöge megkapható egy O(n) komplexitású algoritmus segítségével. Az adott konvex sokszög egy csúcsához U-t rendelünk, ha a csúcs a talált minimális területű beírt sokszögnek is csúcsa és N-et egyébként. Így előállítható egy n-hosszú, egy adott minimális területű beírt sokszög csúcsait megadó sorozat. Bebizonyítjuk, hogy egy U-ból és N-ből álló sorozat pontosan akkor írja le egy n-szög egyik minimális területű beírt sokszögét, ha nem tartalmaz két egymást követő N-et és három egymást követő U-t. Ehhez megadunk egy konstrukciót egy tetszőleges, a fenti tulajdonságot kielégítő sorozathoz tartozó sokszög előállítására. Továbbá megadunk egy O(n^3) komplexitású algoritmust egy adott konvex sokszög minimális kerületű beírt sokszögének megkeresésére. Az adott konvex sokszög egy csúcsához U-t rendelünk, ha az algoritmus által megtalált sokszögnek is csúcsa és N-et egyébként. Megmutatjuk, hogy ha a megtalált minimális kerületű beírt sokszög egy csúcsa belső pontja az adott sokszög egyik oldalának, akkor ebben a csúcsban a beírt sokszög az adott sokszög oldalára nézve kielégíti a visszaverődési törvényt. Így előállítható egy n-hosszú, egy adott minimális kerületű beírt sokszög csúcsait megadó sorozat. Belátjuk, hogy egy U-ból és N-ből álló sorozat pontosan akkor írja le egy n-szög egyik minimális kerületű beírt sokszögét, ha nem tartalmaz három egymást követő U-t. Ehhez billiárd pályák segítségével megadunk egy konstrukciót egy tetszőleges sorozathoz tartozó sokszög előállítására.
[1] M. Ausserhofer et al., „An algorithm to find maximum area polygons circumscribed about a convex polygon”, Discrete Applied Mathematics, Vol. 255, 98-108 (2019).
