Duality for Geometric Set Cover and Geometric Hitting Set Problems on Pseudodisks
Stéphane Durocher, Robert Fraser · 2015
Given an instance of a geometric set cover problem on a set of points X and a set of objects R, the dual is a geo-metric hitting set problem on a set of points P and a set of objects Q, where there exists a one-to-one mapping from each xj ∈ X to a dual object Qj ∈ Q and for each Ri ∈ R to a dual point in pi ∈ P, so that a dual point pi is contained in a dual object Qj if and only if the cor-responding primal point xj is covered by the object Ri. In this work, we explore the setting of geometric dual-ity for geometric set cover problems on pseudodisks. We first show that there does not always exist a geometric dual on pseudodisks. We initiate the search for a char-acterization of the class of objects that may be dualized by identifying a sufficient (but not necessary) property for a dual to exist on distinct pseudodisks, called the pair-cover and crossing-quad free property. We show that such problems may be dualized into hitting set in-stances on pseudodisks by building a planar support for the dual instance, and then constructing an orthogo-nal drawing of the support which we transform into a dual set of pseudodisks. A corollary of these results is a PTAS for dualizable set cover problems using the PTAS for hitting set on pseudodisks. 1