  Suppose we are given a set $\cal B$ of blue points and a set $\cal R$ of red
points, all lying above a horizontal line $\ell$, in the plane. Let the weight
of a given point $p_i\in {\cal B}\cup{\cal R}$ be $w_i>0$ if $p_i\in {\cal B}$
and $w_i<0$ if $p_i\in {\cal R}$, $|{\cal B}\cup{\cal R}|=n$, and
$d^0$($=d\setminus\partial d$) be the interior of any geometric object $d$. We
wish to pack $k$ non-overlapping congruent disks $d_1$, $d_2$, \ldots, $d_k$ of
minimum radius, centered on $\ell$ such that
$\sum\limits_{j=1}^k\sum\limits_{\{i:\exists p_i\in{\cal R}, p_i\in
d_j^0\}}w_i+\sum\limits_{j=1}^k\sum\limits_{\{i:\exists p_i\in{\cal B}, p_i\in
d_j\}}w_i$ is maximized, i.e., the sum of the weights of the points covered by
$\bigcup\limits_{j=1}^kd_j$ is maximized. Here, the disks are the obnoxious or
undesirable facilities generating nuisance or damage (with quantity equal to
$w_i$) to every demand point (e.g., population center) $p_i\in {\cal R}$ lying
in their interior. In contrast, they are the desirable facilities giving
service (equal to $w_i$) to every demand point $p_i\in {\cal B}$ covered by
them. The line $\ell$ represents a straight highway or railway line. These $k$
semi-obnoxious facilities need to be established on $\ell$ to receive the
largest possible overall service for the nearby attractive demand points while
causing minimum damage to the nearby repelling demand points. We show that the
problem can be solved optimally in $O(n^4k^2)$ time. Subsequently, we improve
the running time to $O(n^3k \cdot\max{(\log n, k)})$. The above-weighted
variation of locating $k$ semi-obnoxious facilities may generalize the problem
that Bereg et al. (2015) studied where $k=1$ i.e., the smallest radius maximum
weight circle is to be centered on a line. Furthermore, we addressed two
special cases of the problem where points do not have arbitrary weights.

Computational Geometry