On polygonal covers
Michel Pocchiola, Gert Vegter · Contemporary mathematics - American Mathematical Society · 1999
A polygonal cover of a finite collection of pairwise disjoint convex compact sets in the plane is a finite collection of non-overlapping bounded convex polygons such that each polygon covers exactly one convex set. We show that computing a polygonal cover with worst case minimal number of sides reduces to computing a pseudo-triangulation of the collection of convex sets. We obtain a similar reduction for two related problems concerning convex compact sets in the plane : computing a lighting set and computing a family of separating lines. Our main tool is the notion of screen graph (introduced in this paper) associated with a pseudo-triangulation. Keywords: Pseudotriangle, pseudo-triangulation, screen graph, polygonal cover, translation query, Art gallery theorem, packing, covering. On Polygonal Covers (revised version March 10, 1997) M. Pocchiola & G. Vegter 1 Introduction A polygonal cover of a finite collection of pairwise disjoint convex compact sets in the plane (we refer to a ...