algoritmus
Sok színvonalas megoldása létezik a feladatnak, melyek hol egyszerűbbek, hol bonyolultabbak. Mindazonáltal minden megoldás ugyanazon alapötletre épít: nem szükséges minden egyes pontját megvizsgálni a síknak, elegendő csupán azokon a helyeken, ahol a lapok rétegszáma megváltozik. Ezek a speciális helyek pedig az élek.
Mivel az élek pontjaiból viszonylag sok is lehet, így a különböző algoritmusok további egyszerűsítő módszerekkel redukálják a vizsgálandó pontok halmazát.
Egy lehetséges algoritmus
Az egyik legegyszerűbb megoldás Torma Róbert matematikus kollégától származik:
Minden egyes lap függőleges, illetve vízszintes éleit meghosszabbítva felosztjuk a síkot. Így megközelítőleg $(2N)^2=4N^2$ téglalap alakú terület keletkezik. Belátható, hogy az így kapott téglalapokon belül a lapok száma nem változhat, azaz állandó. Elegendő tehát minden részterület egy tetszőleges pontját (például a bal felső sarokpontot) kiválasztva megvizsgálni, hogy az adott téglalapot összesen hány lap tartalmazza.
Ez a megoldás nem a leghatékonyabb, mivel minden esetben közel $4N^2\cdot N=4N^3$ lépésszámot használ. Ugyanakkor kivitelezése nagyon egyszerű, és nem sokkal rosszabb az eddig ismert legjobb, $O(N^2\log N)$-es algoritmusoknál.
Kódok
