Personal tools
You are here: Home CG seminar 2019 Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains
« February 2019 »
February
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
2425262728
Log in


Forgot your password?
 

Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains

Wednesday, December 19th, 2018, 16:10

Schreiber 309

underline

Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains

Matya Katz, BGU

Abstract:

A graph G = (V,E) is terrain-like if one can assign a unique integer from the range [1..|V|] to each vertex in V, such that, if both {i,k} and {j,l} are in E, for i < j < k < l, then so is {i,l}. We present a local-search-based PTAS for minimum dominating set in terrain-like graphs. Then, we observe that, besides the visibility graphs of x-monotone terrains which are terrain-like, so are the visibility graphs of weakly-visible polygons and weakly-visible terrains, immediately implying a PTAS for guarding the vertices of such a polygon or terrain from its vertices. We also present PTASs for continuously guarding the boundary of a WV-polygon or WV-terrain, either from its vertices, or, for a WV-terrain, from arbitrary points on the terrain. Finally, we compare between terrain-like graphs and non-jumping graphs (Ahmed et al., 2017), answering a question concerning the latter family, and observing that both families admit PTASs for maximum independent set.

 
 
Document Actions