I sitt seminala arbete med homologiska sensornätverk visade de Silva och Ghrist det överraskande faktum att det är möjligt att certifiera täckningen av ett koordinatfritt sensornätverk även med mycket minimal kunskap om det utrymme som ska täckas. Här innebär täckning att varje punkt i domänen (utom möjligen de mycket nära gränsen) har en närliggande sensor. Mer allmänt, deras algoritm tar ett par bon grannskapet grafer tillsammans med en märkning av hörn som antingen gräns eller interiör och beräknar den relativa homologin av ett simplicial komplex som induceras av graferna. Detta tillvägagångssätt, som kallas Topological Coverage Criterion (TCC), kräver vissa antaganden om den underliggande geometriska domänen samt vissa antaganden om förhållandet mellan inmatningsgraferna till domänen. Syftet med detta dokument är att generalisera dessa antaganden och visa hur TCC kan tillämpas på både mycket mer allmänna områden samt mycket svaga antaganden om input. Vi ger ett nytt, enklare bevis på de Silva-Ghrist Topological Coverage Criterion som eliminerar alla antaganden om smidigheten i gränsen av det underliggande utrymmet, vilket gör att resultaten kan tillämpas på mycket mer allmänna problem. De nya bevisfaktorerna för geometriska, topologiska och kombinatoriska aspekter gör det möjligt för oss att tillhandahålla ett täckningstillstånd som stöder tjocka gränser, k-täckning och viktad täckning, där sensorerna har varierande radier. Problem i Homological Sensor Networks (HSNs) brukar anges i ordförrådet i sensornätverk. Det finns sensorer och täckning regioner, och ett viktigt problem är att avgöra om den sensoriska regionen av en samling sensorer täcker en given domän, med tanke på endast grannskapet relationer mellan sensorerna och någon indikation på vilka sensorer är nära gränsen. Punkternas placeringar (koordinater) antas inte, och inte heller ska domänens form (topologi) täckas. Även om problemet formuleras på sensornätverkens språk, kan det uppfattas mer allmänt som en del av datatäckningen; det svarar när en datamängd * Stöds av NSF beviljar CCF-1464379 och CCF-1525978. † University of Connecticut. "University of Connecticut" (universitetet i Connecticut). § Universitetet i Connecticut. tillräckligt täcker en domän, och hål i täckningen kan ses som luckor i data. Ett överraskande resultat av de Silva & Ghrist är att det finns ett beräkningsbart, tillräckligt tillstånd som kallas Topological Coverage Criterion (TCC) för att certifiera täckning utan att veta var sensorerna finns när domänens gräns är jämn [4]. Allt som krävs är att sensorerna har unika identifierare, kan upptäcka närliggande sensorer, kan differentiera om angränsande sensorer är "nära" eller "mycket nära" (i teknisk mening som ska definieras nedan), och kan upptäcka om gränsen för domänen är nära. Utvecklad över en serie av papper [8, 17, 5, 4], den mest allmänna versionen av TCC kan förstås som ett rent geometriskt problem på punkt sätter P i R d med okända koordinater i en okänd domän D. Ingången är bara ett par bon grannskap grafer på de punkter som anger vilka punkter är nära som andra och en märkning av de punkter som anger vilka punkter som är nära gränsen för D. Bestämning täckning är illa placerad med endast denna information, men de Silva & Ghrist bevisade att TCC ger ett tillräckligt villkor för täckning (av en något krympt version) av domänen när radien är alla lika, gränsen av domänen är en jämn mångfald med avgränsad injiceringsradie, och målet är att certifiera enkel täckning (varje punkt omfattas av minst en sensor). I detta dokument generaliserar vi dessa resultat i flera riktningar, framför allt genom att eliminera många av de geometriska antagandena på domänen, samtidigt som vi certifierar flera täckningar och möjliggör varierande radi. För en ingångsgraf G = (P, E) där P är en uppsättning punkter, och en delmängd Q P av punkter som märkts som nära gränsen, TCC algoritm bygger ett par simplial komplex, en från kliques i G och en från kliques i subgraph av G inducerad av Q. Genom en enkel matrisreduktion kan ett vektorutrymme som kallas den relativa d-dimensionella homologin hos detta par av underkomplex beräknas. I en idealisk situation skulle dimensionen ange exakt antalet anslutna komponenter om och endast om domänen omfattas. Detta förenklade tillvägagångssätt fungerar dock inte i allmänhet, eftersom det kan upptäcka falska komponenter. Insikten i de Silva och Ghrist var att visa att för tillräckligt fina geometriska
Cavanna m.fl. Ref generaliserade nyligen antagandena om gränserna för att göra resultaten tillämpliga på allmänna områden.
When and why the topological coverage criterion works
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}