A Hill-Beck földmegosztási probléma a Tad Hill által 1983-ban javasolt méltányos tortavágás probléma egy változata [1] .
Van egy D terület n országgal szomszédos . Minden ország megbecsüli (a maga módján) a D terület részhalmazait . Az országok igazságosan akarják felosztani a D területet egymás között, ahol a "méltányosság" arányos felosztást jelent . Ezen túlmenően, az egyes országokhoz kiosztott részeknek kapcsolódniuk kell a kijelölt országhoz és szomszédosnak kell lenniük . Ezek a földrajzi korlátok különböztetik meg a problémát a klasszikus méltányos tortavágás problémájától .
Formálisan bármely C i országnak meg kell kapnia a D terület diszjunkt darabjait , amelyeket D i -vel jelölünk úgy, hogy a C i és D közötti határ egyes részei benne legyenek .
Vannak esetek, amikor a probléma nem oldható meg:
Hill 1983-ban bebizonyította, hogy ha D -ben minden egyes pont értéke 0 minden országra, és D határa minden országra 0, akkor van egy arányos osztás, amelyre szomszédsági megszorítások vonatkoznak. Bizonyítása csak a létezésre vonatkozott, algoritmust nem mutatott be [1] .
Négy évvel később Anatole Beck leírt egy protokollt egy ilyen felosztás elérésére [2] . Lényegében a protokoll az „ utolsó minimum ” protokoll továbbfejlesztése. A jegyzőkönyv lehetővé teszi az országok számára, hogy a D terület egyes részeire jelentkezzenek, a legkisebb kérelmet benyújtó részt adja a kérelmezőnek, a fennmaradó részt pedig felosztja a fennmaradó országok között. Némi változtatásra van szükség a szomszédsági korlátozások teljesülésének biztosításához.
Ha a D terület egyszerűen össze van kötve , akkor a következő algoritmust használjuk:
Két eset van.
Egyetlen győztes4. Ha D 1 -et csak egy ország rajzolja ki, mondjuk C i , akkor a lemezt C i országnak adjuk . Értéke más országokban szigorúan kisebb, mint , így C i országnak adhatunk egy kis extra darabot a lefoglalt lemez mellett.
Ehhez rajzoljunk egy szektort, amely összeköti D 1 -et a D kör határával . Hagyja, hogy minden ország (kivéve C i ) válasszon ki ebből a szektorból, hogy a lemez és a szektor együttes értéke ne haladja meg a . Ez azzal a feltétellel lehetséges, hogy az origótól számított összes sugár értéke 0. Adjuk meg C i országnak a D 1 és a csonka szektor unióját .
A fennmaradó terület egyszerűen össze van kötve, és legalább a fennmaradó országok számára értéke van, így a felosztás rekurzív módon folytatható az 1. lépéstől.
Több nyertesHa a D 1 részt k >1 ország kérte , akkor néhány kifinomultabb aukcióra van szükség ahhoz, hogy megtaláljuk azt az országot, amelyhez megadhatjuk a lemezt és a hivatkozási szektort.
5. Válasszunk ki egy tetszőlegesen győztes országot, és nevezzük deklarátornak , C 1 . Kérje meg, hogy adjon hozzá egy szektort, amely összeköti a D 1 -et jelenlegi területével, és hagyja, hogy a többi ország elszakadjon ettől a szektortól, így:
6. Minden nyertes ország javasoljon új r sugarat (kisebbet, mint az eredeti javaslat), így a szektor levágott részének és az r sugarú korongnak az értéke pontosan . A legkisebb ilyen D 2 lemezt választjuk . Ismét két eset van:
Ha C 1 a D 2 -re jelentkező országok egyike , akkor egyszerűen megadjuk neki a D 2 területet (ami valamivel kisebb, mint az eredeti D 1 kérelem ) és a csatlakozó szektort. C 1 egyetért azzal, hogy az érték , és más országok egyetértenek abban, hogy az érték nem nagyobb, mint , így folytathatjuk rekurzív módon az 1. lépéstől.
Ellenkező esetben C 1 egyetért azzal, hogy D 2 és az összekötő szektor összértéke kisebb, mint . Ezzel minden vesztesnek egyet kell értenie, mivel D 2 kisebb, mint D 1 . Így a C 1 és minden más ország, amely egyetért ezzel, kikerül a nyertesek sorából.
7. A fennmaradó nyertesek közül új C 2 pályázót választunk . Adjon hozzá egy másik szektort, amely összeköti a D 2 -t az aktuális területtel, és hagyja, hogy más országok csonkolják ezt a szektort, mint az 5. lépésben.
Jegyezzük meg, hogy most a D 2 terület két területtel van összekötve - C 1 és C 2 . Ez probléma, mivel a terület többi részét inkoherenssé teszi. A probléma megoldására C 2 választhat egy másik szektort, amelynek hossza kisebb, mint 1, hogy ne szakítsa meg a kapcsolatot [2] . Ezt a harmadik szektort ismét minden ország csonkolja, mint az 5. lépésben. Válaszul a C 2 -nek vissza kell adnia a D 2 -t a C 1 -gyel összekötő szektor egy részét , amelynek értéke megegyezik a fogadott harmadik értékével. ágazat.
A C 2 ország által javasolt vágás most a következő részeket tartalmazza: D 2 , egy 1 hosszúságú szektor, amely összeköti a D 2 -t a C 2 -vel , és két rövid szektor, amelyek nem érik el a D határát . Ennek a konstrukciónak az értéke C 2 -re egyenlő , a veszteseknél az érték kisebb, mint , és a többi nyertesnél nem haladja meg a -t .
Ez a folyamat a fennmaradó nyertesekkel folytatódik, amíg csak egy nyertes marad.
Ha a D terület k -összekötve véges k -vel, akkor az osztás k -on történő indukcióval elvégezhető .
Ha D csatlakoztatva van és felosztható az előző szakasz protokolljával.
Ellenkező esetben jelölje D külső határát B 1 - nek , belső határait pedig .
Megtaláljuk a B 1 külső határt a B k belső határral összekötő L egyenest úgy, hogy ennek az L vonalnak az értéke minden ország esetében 0. Ezt a következő érv alapján tehetjük meg. Megszámlálhatatlan számú páronként nem metsző egyenes van, amely összeköti a B 1 -et és a B k -t D -ben . De a mértékük D -ben véges, tehát a pozitív mértékû sorok számának megszámlálhatónak kell lennie, és akkor van egy nulla mértékû egyenes.
A készlet -csatlakozik . Bontsuk fel rekurzív módon, majd rendeljük tetszőlegesen L -t bármely országhoz, amellyel ez a terület határos. Ez nem sérti az osztás igazságosságát, mivel az L értéke minden országra 0.