We study a general family of facility location problems defined on planar graphs and on the
2-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying …

We investigate the family of intersection graphs of low density objects in low dimensional
Euclidean space. This family is quite general, includes planar graphs, and in particular is a …

We are given a set of weighted unit disks and a set of points in Euclidean plane. The
minimum weight unit disk cover (WUDC) problem asks for a subset of disks of minimum total …

We present a (1+ ε)-approximation algorithm with quasi-polynomial running time for
computing a maximum weight independent set of polygons from a given set of polygons in …

Weighted geometric set-cover problems arise naturally in several geometric and non-
geometric settings (eg the breakthrough of Bansal and Pruhs (FOCS 2010) reduces a wide …

We describe how to approximate, in quasi-polynomial time, the largest independent set of
polygons, in a given set of polygons. Our algorithm works by extending the result of …

We consider a variant of the art gallery problem where all guards are limited to seeing
180degree. Guards that can only see in one direction are called half-guards. We give a …

Given a set P of n points in the plane, Covering Points by Lines is the problem of finding a
minimum-cardinality set L of lines such that every point p∈ P is incident to some line ℓ∈ L …

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 geometric hitting set problem on a set of points P and a set of objects Q …

Abstract Recently, Adamaszek and Wiese [1, 2] presented a quasi-polynomial time
approximation scheme (QPTAS) for the problem of computing a maximum weight …