Discretization of Planar Geometric Cover Problems

الأصل · EN

We consider discretization of the 'geometric cover problem' in the plane: Given a set P of n points in the plane and a compact planar object T₀, find a minimum cardinality collection of planar translates of T₀ such that the union of the translates in the collection contains all the points in P. We show that the geometric cover problem can be converted to a form of the geometric set cover, which has a given finite-size collection of translates rather than the infinite continuous solution space of the former. We propose a reduced finite solution space that consists of distinct canonical translates and present polynomial algorithms to find the reduce solution space for disks, convex/non-convex polygons (including holes), and planar objects consisting of finite Jordan curves.