Rectilinear and polygonal p-piercing and p-center problems

We consider the p-piercing problem, in which we are givena collection of regions, and wish to determine whether thereexists a set of p points that intersects each of the given regions.We give linear or near-linear algorithms for smallvalues of p in cases where the given regions are either axisparallelrectangles or convex c-oriented polygons in the plane(i.e., convex polygons with sides from a fixed finite set of directions).We also investigate the planar rectilinear (and polygonal)...