Terrain Guarding Problem(TGP), som är känd för att vara NP-komplett, ber att hitta en minsta uppsättning av skydd platser på en terräng T sådan att varje punkt på T är synlig av en vakt. Här studerar vi detta problem på 1.5D ortogonal terräng där kanterna är bundna till att vara horisontella eller vertikala. Vi föreslår en 2- approximation algoritm som körs i O(n log m) tid, där n och m är storleken på input respektive utdata, respektive. Detta är en förbättring jämfört med den tidigare bästa algoritmen, som är en 2- approximation med O(n 2 ) körtid.
Lyu ochÜngör REF formulerade en 2-ungeling algoritm för ortogonal terräng bevakning problem som körs i O(nlogm), där m är utdatastorleken.
A Fast 2-Approximation Algorithm for Guarding Orthogonal Terrains
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}