Antag att hela planet (eller en stor region) övervakas av en uppsättning S stationära sensorer så att varje element s. S kan observera en axel-parallell enhet kvadrat R(s) centrerad vid s, som kallas intervallet för s. Varje sensor är utrustad med ett batteri av enhetens livslängd. Är det sant att om varje punkt i planet tillhör räckvidden av många sensorer, då kan vi övervaka planet under en lång tid utan att få slut på ström? Om S kan delas upp i k delar S1, S2,. .., S k sådan att, för varje i, sensorerna i Si tillsammans kan observera hela planet, då planet kan övervakas utan avbrott för k enheter av tid. Vi kan först slå på alla sensorer som tillhör S1. När dessa sensorer har slut på batteri kan vi slå på alla delar av S2, etc. Vi kommer fram till följande problem. Låt m(k) betecknar det minsta positiva heltal m sådan att varje m-faldig täckning av planet med axel-parallell enhet kvadrater delas i minst k täcker. Vi visar att m(k) = O(k 2 ), och generalisera detta resultat för att översätta alla centralt symmetriska konvex polygon i stället för kvadrater. Från andra hållet vet vi bara att m(k) ≥ 4k/3 − 1.
Pach och Tóth REF visade att ett t-faldigt omslag av översättningar av en centralt-symmetrisk öppen konvex polygon kan brytas ned i (e) omslag.
Decomposition of multiple coverings into many parts
{'venue': "SCG '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}