Abstrakt. Vi studerar problemet med att täcka en tvådimensionell rumslig region P, belamrat med ockluders, av sensorer. En sensor placerad på en plats p täcker en punkt x i P om x ligger inom avkänningsradie r från p och x är synlig från p, dvs segmentet px inte skär någon occluder. Målet är att beräkna en placering av det minsta antalet sensorer som täcker P. Vi föreslår en landmärkesbaserad metod för att täcka P. Antag att P har hål, och det kan täckas av h sensorer. Med tanke på en liten parameter ε > 0, låt λ := λ(h, ε) = (h/ε) log  och Vi bevisar att man kan beräkna en uppsättning L av O(λ log λ log (1/ε)) landmärken så att om en uppsättning S sensorer täcker L, då S täcker minst (1 − ε)-fraktion av P. Det är förvånande att så få landmärken behövs, och att antalet inte beror på antalet hörn i P. Vi presenterar sedan effektiva randomiserade algoritmer, baserat på den giriga tillvägagångssätt, att, med hög sannolikhet, beräkna O(h log λ) sensor platser för att täcka L; härh ≤ h är antalet sensorer som behövs för att täcka L. Vi föreslår olika förlängningar av vår strategi, inklusive: (i) en vikt funktion över P ges och S bör täcka minst (1 − ε) av det viktade området i P, och (ii) varje punkt av P täcks av minst t sensorer, för en given parameter t ≥ 1.
Relaterad, Agarwal et al. REF föreslår en girig landmärkesbaserad metod som löser för placeringen av det minsta antal fyrar (inom en loggfaktor) som krävs för att täcka alla utom en bråkdel av en given polygonal miljö.
Efficient sensor placement for surveillance problems
{'venue': 'DCOSS', 'journal': None, 'mag_field_of_study': ['Computer Science']}