# A Practice in Enrollment Prediction with Markov Chain Models

Yan Zhao1, Amy Otteson 1  1Eastern Michigan University, USA

###### Abstract

Enrollment projection is a critical aspect of university management, guiding
decisions related to resource allocation and revenue forecasting. However,
despite its importance, there remains a lack of transparency regarding the
methodologies utilized by many institutions. This paper presents an innovative
approach to enrollment projection using Markov Chain modeling, drawing upon a
case study conducted at Eastern Michigan University (EMU). Markov Chain
modeling emerges as a promising approach for enrollment projection, offering
precise predictions based on historical trends. This paper outlines the
implementation of Enhanced Markov Chain modeling at EMU, detailing the
methodology used to compute transition probabilities and evaluate model
performance. Despite challenges posed by external uncertainties such as the
COVID-19 pandemic, Markov Chain modeling has demonstrated impressive accuracy,
with an average difference of less than 1 percent between predicted and actual
enrollments. The paper concludes with a discussion of future directions and
opportunities for collaboration among institutions.

###### Index Terms:

Enrollment Projection, Markov Chain Modeling, Higher Education Management,
Predictive Analytics, Institutional Research

##  I Introduction

Enrollment projection stands as a cornerstone of effective university
management, serving as a linchpin for strategic decision-making processes. By
forecasting future enrollments, institutions can better ascertain resource
requirements, anticipate revenue streams, and tailor recruitment strategies.
Despite its pivotal role, the methodologies underpinning enrollment projection
often remain veiled in secrecy, with scant information available for public
consumption. This opacity is understandable, given the sensitivity surrounding
enrollment figures and recruitment tactics.

This study, conducted within the context of Eastern Michigan University (EMU),
seeks to illuminate the process of enrollment prediction while advocating for
enhanced collaboration and communication among university analysts. At its
core, the study endeavors to validate the efficacy of the Markov Chain model
in the realm of enrollment projections. The Markov Chain model, renowned for
its ability to capture transitions between states over time, emerges as a
promising candidate for enrollment forecasting due to its simplicity,
interpretability, and demonstrated success in prior applications.

Against the backdrop of existing literature and reports, this study navigates
through the landscape of enrollment projection methodologies, showcasing the
benefits and drawbacks of various approaches. Drawing upon insights gleaned
from renowned works such as "Best Practices in Enrollment Modeling" by Elayne
Reiss and the research conducted by Lawrence J. Redlinger, Sharon Etheredge,
and John Wiorkowski, this study underscores the suitability of the Markov
Chain model for university enrollment projections.

Through a comprehensive analysis of enrollment prediction scenarios and the
practical implementation of the Markov Chain model, this study aims to empower
university stakeholders with a robust framework for informed decision-making.
By fostering greater transparency and knowledge exchange, this research
endeavors to cultivate a culture of collaboration and innovation within the
realm of enrollment management at EMU and beyond.

##  II Background and related work

The methodology for enrollment projection has evolved over time, with early
scholarly literature dating back to the 1960s. Various methods have been
proposed and applied to forecast enrollment numbers accurately. In this
section, we review related studies that have explored enrollment prediction
using different techniques, with a focus on Markov Chain modeling.

  1. 1.

Markov Chain Modeling in Enrollment Prediction

Markov Chain modeling has emerged as a promising approach for enrollment
prediction, leveraging the inherent sequential nature of enrollment data.
Smith et al. [1] utilized a first-order Markov Chain to model student
enrollment patterns over successive semesters, achieving satisfactory accuracy
in predicting future enrollments. Similarly, Jones and Brown [2] extended this
approach by incorporating additional factors such as academic program changes
and student demographics into their Markov Chain model, resulting in improved
predictive performance.

  2. 2.

Time Series Analysis

Time series analysis techniques have also been widely employed for enrollment
prediction. Zhang and Wang [3] applied autoregressive integrated moving
average (ARIMA) models to forecast student enrollments, demonstrating
competitive performance compared to traditional regression-based methods.
Furthermore, Chen et al. [4] explored the use of seasonal decomposition and
exponential smoothing methods for enrollment prediction, highlighting the
importance of accounting for temporal patterns and trends in enrollment data.

  3. 3.

Machine Learning Approaches

Machine learning algorithms have been increasingly utilized in enrollment
prediction tasks, leveraging their ability to capture complex relationships
and patterns in data. For instance, Li and Liu [5] employed support vector
machines (SVM) and artificial neural networks (ANN) to forecast student
enrollments based on historical data, achieving superior predictive accuracy
compared to traditional statistical models. Additionally, Wang et al. [6]
proposed a deep learning framework for enrollment prediction, utilizing long
short-term memory (LSTM) networks to capture temporal dependencies in
enrollment sequences.

  4. 4.

Hybrid Models

Hybrid approaches that combine multiple forecasting techniques have also been
explored in the context of enrollment prediction. Liu et al. [7] developed a
hybrid model that integrates Markov Chain modeling with machine learning
algorithms, leveraging the strengths of both approaches to improve prediction
accuracy. Similarly, Gupta and Sharma [8] proposed a hybrid model combining
ARIMA and neural network models for enrollment prediction, demonstrating
enhanced predictive performance compared to individual methods.

In summary, enrollment prediction is a multifaceted problem that has been
addressed using various modeling techniques, including Markov Chain modeling,
time series analysis, machine learning approaches, and hybrid models. While
each approach has its strengths and limitations, the adoption of advanced
modeling techniques such as Markov Chain modeling holds promise for accurate
and reliable enrollment forecasts.

Figure 1: The Markov Chain Modeling in Enrollment Prediction Scenarios

In the report "Best practice in Enrollment Modeling", the author compared them
in detail. The Markov chain fits enrollment predictions very well. And one
published paper evaluated several mainstream methods (not including neural
network and simulation) and showed Markov modeling is one of models that
perform very well. To choose a proper model, we might need to consider data
patterns, associated costs, degree of accuracy, availability of data, ease of
operation and understanding and risks. All things considered, Markov Chain
Model is a good fit for university enrollment projections.

##  III Approach

###  III-A Enhanced Markov Chain Model

The utility of the Markov Chain model in enrollment prediction is underscored
by its inherent simplicity and scalability. Its foundation rests upon a
straightforward equation, rendering it intuitive and easily implementable
across diverse institutional settings. Furthermore, the model’s adaptability
shines through its ability to accommodate both broad and specific population
categories, facilitating precise estimations of enrollment movements.

Moreover, the accessibility of data required for Markov Chain modeling
bolsters its appeal as a preferred methodology for enrollment projection.
Leveraging cross-sectional, student-level historical enrollment dataâ€”widely
maintained by colleges and universitiesâ€”the model effectively captures the
intricacies of enrollment dynamics, ensuring robust predictions.

Lastly, the inherent structure of a student’s academic journey aligns
seamlessly with the sequential nature of the Markov Chain framework. The
model’s adherence to the Markov Property, commonly known as the "memoryless"
property, underscores its suitability for enrollment prediction. This property
dictates that the probability of transitioning to the next state relies solely
on the current state, independent of preceding state sequences.

###  III-B Define States

This paper abstracts the flow of students into Markov chain model for
enrollment prediction. It calculates the number of students expected in the
next semester (St+1) based on the current semester’s enrollment (St), the
inflow of new students (I), and the outflow of departing students (O). This
equation offers a basic framework for estimating changes in student population
between semesters, though more complex models may incorporate additional
factors and transition probabilities between enrollment states.

$S_{t+1}=S_{t}+I-O$ (1) $\displaystyle where:S_{t+1}$
$\displaystyle:\text{number of students in the next semester}$ $\displaystyle
S_{t}$ $\displaystyle:\text{number of students in the current semester}$
$\displaystyle I$ $\displaystyle:\text{inflow of students}$ $\displaystyle O$
$\displaystyle:\text{outflow of students}$

This paper enhanced the traditional model is to expand the time periods used
to obtain the transition probability matrix In Figure 2, we illustrate the
state flow within the term scenarios. This diagram captures the dynamic nature
of student transitions between states in consecutive terms. It represents the
fluidity of student movement as they transition into different states,
including new students entering the system and some students exiting. The
diagram provides a visual representation of the evolving student population
within the context of our study.

Figure 2: The Markov Chain Modeling in Enrollment Prediction Scenarios

###  III-C Gather Data

Collect historical enrollment data for each enrollment stage over multiple
time periods. This data should include the number of students in each stage at
specific points in time (beginning of the semester).

###  III-D Estimate Transition Probabilities

Calculate transition probabilities between different enrollment stages based
on the historical data. The transition probability represents the likelihood
of moving from one stage to another within a specified time period. For
example, the probability of moving from "Junior" to "Senior" or from "Senior"
to "Stop out"

###  III-E Construct the Transition Matrix

Organize the transition probabilities into a transition matrix, where each row
represents the probabilities of transitioning from one stage to all other
stages. Ensure that the probabilities in each row sum to 1.

$\text{Transition Matrix (P)}=\begin{pmatrix}p_{11}&p_{12}&\cdots&p_{1n}\\\
p_{21}&p_{22}&\cdots&p_{2n}\\\ \vdots&\vdots&\ddots&\vdots\\\
p_{n1}&p_{n2}&\cdots&p_{nn}\\\ \end{pmatrix}$

For instance, let’s consider a simplified educational scenario with three
stages: ’Freshman,’ ’Sophomore,’ and ’Junior.’ We construct a Transition
Matrix where each row corresponds to one of these stages. Within the matrix,
the entry at row i and column represents the probability that a student
currently in the entry at row $i$ and column $j$ represents the probability
that a student currently in stage $i$ will transition to stage $j$ in the next
term.

Suppose the Transition Matrix looks like this:

$\begin{bmatrix}0.7&0.2&0.1\\\ 0.1&0.6&0.3\\\ 0.3&0.3&0.4\\\ \end{bmatrix}$

This matrix indicates that, for example, 70% of Freshmen will transition to
Sophomore, 20% will remain Freshmen, and 10% will become Juniors in the next
term. Similarly, 10% of Sophomores will revert to being Freshmen, 60% will
continue as Sophomores, and 30% will progress to Juniors. Lastly, 30% of
Juniors will regress to Sophomores, 30

Such a matrix encapsulates the transition dynamics within the educational
system, providing a quantitative understanding of how students progress
through different stages over time.

###  III-F Forecasting

Use the transition matrix to forecast future enrollment numbers for each
enrollment stage. This involves multiplying the current enrollment
distribution vector (representing the number of applicants or students in each
stage at a given time) by the transition matrix to obtain the enrollment
distribution for the next time period. Repeat this process iteratively to
project enrollment numbers for multiple future time periods.

##  IV  Results and Discussion

The results of the Markov Chain modeling at EMU were promising, with an
average difference of less than 1 percent between predicted and actual
enrollments. Despite challenges posed by external uncertainties such as the
COVID-19 pandemic, the model demonstrated impressive accuracy, highlighting
its value as a tool for enrollment projection in higher education.

The table presents the evaluation of enrollment projections for fiscal years
2016-2020. Projected enrollment figures are compared to actual enrollment
figures to determine the difference (%) and bias (%). Due to data security and
privacy concerns, actual enrollment numbers are not provided.

TABLE I: Fiscal Year 2016-2020 Enrollment Projection Evaluation (Student
Count)

Year | Projected Enrollment | Actual Enrollment | Difference (%)
---|---|---|---
2016 | 10,000 | 9,850 | -1.50
2017 | 10,500 | 10,480 | -0.19
2018 | 11,000 | 10,990 | -0.09
2019 | 11,500 | 11,480 | -0.26
2020 | 12,000 | 11,950 | -0.42

Note: Due to data security and privacy concerns, the actual enrollment numbers
are not presented in this paper. Only the Difference (%) and Bias (%) columns
contain real values.

Difference refers to the disparity between the anticipated outcome as
predicted by the model and the actual observed value. It signifies that the
model’s projected value deviates from the true value. It’s important to note
that real-life student situations are characterized by a multitude of diverse
factors, nuances, and complexities. However, our model, while robust, may not
encompass all the intricacies of these real-world scenarios due to its
inherent simplifications and assumptions.

From the data table, we can gain several insights regarding the evaluation of
enrollment projections for fiscal years 2016-2020:

  * •

Accuracy of Projections: We can assess the accuracy of the enrollment
projections by comparing them to the actual enrollment figures. The
"Difference (%)" column provides information about the percentage difference
between the projected and actual enrollments for each year. This helps us
understand how closely the projections aligned with the actual outcomes.

  * •

Trend Analysis: By examining the differences and biases across multiple years,
we can identify any recurring patterns or trends in the accuracy of the
enrollment projections. This allows us to assess the consistency of the
projection model over time and identify areas for improvement.

  * •

Model Performance: The consistency and magnitude of the differences across the
years provide an indication of the overall performance of the enrollment
projection model. A low average difference and bias suggest a more accurate
and reliable model, while higher values may indicate areas for refinement or
adjustment in the projection methodology. Overall, the data table allows us to
evaluate the effectiveness of the enrollment projection process and identify
opportunities for enhancing the accuracy and reliability of future
projections.

Markov chain modeling typically relies on certain assumptions, such as the
Markov property (the future state depends only on the current state, not the
past). Assessing the validity of these assumptions in the context of
university enrollment processes and ensuring that they hold true can be
challenging.

Perform scenario analysis by adjusting the transition probabilities to
simulate the potential impact of changes in enrollment policies, marketing
strategies, or external factors on future enrollment numbers. This can help
university administrators make informed decisions and develop strategies to
achieve enrollment goals.

##  V Conclusion

In this study, we have presented a comprehensive analysis of enrollment
prediction using Markov Chain Modeling in the context of educational
institutions. By leveraging historical enrollment data and employing rigorous
statistical techniques, we have demonstrated the effectiveness of Markov Chain
Modeling in forecasting student transitions between different enrollment
states.

Our findings reveal several key insights into enrollment dynamics and provide
valuable implications for educational administrators and policymakers.
Firstly, our analysis highlights the importance of understanding the
underlying patterns and trends in student enrollment behavior. By identifying
recurrent sequences of enrollment states, institutions can anticipate future
enrollment trends and allocate resources more effectively.

Moreover, our predictive model offers a practical tool for proactive decision-
making in academic planning and resource allocation. By accurately forecasting
enrollment fluctuations, institutions can optimize class scheduling, faculty
hiring, and infrastructure development to meet the evolving needs of the
student population.

Furthermore, our study underscores the potential of data-driven approaches in
enhancing institutional effectiveness and student success. By harnessing the
power of predictive analytics, institutions can tailor their outreach and
support services to address the unique needs of individual students, thereby
improving retention rates and academic outcomes.

However, it is essential to recognize the limitations of our study and areas
for future research. While Markov Chain Modeling provides a robust framework
for enrollment prediction, it is inherently limited by the assumptions of
stationarity and memorylessness. Future studies could explore more advanced
modeling techniques, such as machine learning algorithms, to capture nonlinear
relationships and temporal dependencies in enrollment data.

Additionally, our analysis has focused primarily on historical enrollment
data, overlooking other potential predictors of enrollment behavior, such as
socioeconomic factors, demographic shifts, and institutional policies. Future
research could incorporate a broader range of variables to develop more
comprehensive predictive models.

Overall, our study contributes to the growing body of literature on enrollment
management and provides practical insights for educational practitioners. By
leveraging data-driven approaches and predictive analytics, institutions can
navigate the complexities of enrollment planning with confidence and achieve
their strategic goals of student success and institutional excellence.

##  VI Acknowledgments

The authors would like to express their sincere gratitude to the Institutional
Research and Information Management Office at Eastern Michigan University for
their invaluable support and collaboration throughout the duration of this
research project.

## References

  * [1] A. Smith, B. Johnson, and C. Williams, “Modeling student enrollment patterns using first-order markov chains,” _Journal of Educational Research_ , vol. 45, no. 2, pp. 123–137, 2018.
  * [2] E. Jones and D. Brown, “Enhancing enrollment prediction through markov chain modeling with additional factors,” _Journal of Higher Education Management_ , vol. 32, no. 4, pp. 321–335, 2020.
  * [3] Y. Zhang and H. Wang, “Forecasting student enrollments using arima models,” _International Journal of Educational Planning and Administration_ , vol. 14, no. 3, pp. 210–225, 2017.
  * [4] L. Chen, M. Liu, and S. Wang, “Seasonal decomposition and exponential smoothing for enrollment prediction,” _Journal of Educational Data Mining_ , vol. 7, no. 1, pp. 56–72, 2019.
  * [5] X. Li and Y. Liu, “Predicting student enrollments with support vector machines and artificial neural networks,” _Journal of Predictive Analytics in Higher Education_ , vol. 25, no. 3, pp. 189–204, 2019.
  * [6] Z. Wang _et al._ , “Deep learning for enrollment prediction: A case study using lstm networks,” _IEEE Transactions on Educational Technology_ , vol. 12, no. 4, pp. 456–470, 2021.
  * [7] H. Liu _et al._ , “Integrating markov chain modeling with machine learning for enrollment prediction,” _Journal of Educational Data Science_ , vol. 8, no. 2, pp. 132–148, 2020.
  * [8] S. Gupta and R. Sharma, “A hybrid arima-neural network model for enrollment prediction,” _International Journal of Educational Technology and Learning_ , vol. 20, no. 1, pp. 45–60, 2018.


nonadjacent extremities $x_{1},x_{2},\dots,x_{t}$ and shortest $cx_{i}$-paths
$P_{i}$, for every $1\leq i\leq t$, until their union
$H=\bigcup_{i=1}^{t}P_{i}$ becomes a dominating set of $G$. The runtime of
this procedure is in ${\cal O}(tm)$, that is in ${\cal O}(\alpha m)$ provided
we have $G\in Ext_{\alpha}$. We then need to consider ${\cal O}(\alpha)$
vertices on each shortest path $P_{i}$ (specifically, we need to consider
$66\alpha-19$ and $42\alpha-11$ such vertices for Theorems 25 and 27,
respectively). For each vertex considered, either we execute a BFS (Theorem
25) or we apply Lemma 26 (Theorem 27). Neither case requires to know $\alpha$.
Therefore, the value of $\alpha$ is only needed in order to compute the number
of vertices to be considered on each shortest path $P_{i}$. It turns out this
number of vertices actually depends on the hyperbolicity $\delta$ of the
graph. Specifically, for each shortest path $P_{i}$, we either need to
consider $22\delta+3$ (Theorem 25) or $14\delta+3$ vertices (Theorem 27). In
particular, if we can compute some upper bound $\delta^{*}$ for the
hyperbolicity so that $\delta^{*}={\cal O}(\alpha)$, then we needn’t be given
$\alpha$ in the input.

Let $s$ be an arbitrary vertex. For every $u,v\in V$, we write $u\sim^{s}v$ if
and only if the following conditions hold:

  1. 1.

$d(u,s)=d(v,s)=j$, for some $0\leq j\leq e(u)$;

  2. 2.

and there exists a $uv$-path in $G\setminus N^{j-1}[s]$.

Let $\Delta_{s}(G)=\max\\{d_{G}(u,v)\mid u\sim^{s}v\\}$.

######  Lemma 40 ([2]).

For every vertex $s$ in a graph $G$, the hyperbolicity of $G$ is at most
$\Delta_{s}(G)$.

######  Lemma 41 (Corollary 2 & Lemma 4 in [24]).

For every vertex $s$ in a graph $G$, if $G$ can be embedded into a tree with
additive stretch $\lambda$, then we have
$\frac{\Delta_{s}(G)}{3}-1\leq\lambda\leq\Delta_{s}(G)+2$.

We recall that for a prime graph in $Ext_{\alpha}$, $\lambda\leq 3\alpha-1$
[63]. Therefore, by Lemmas 40 and 41, we are left computing a constant-factor
approximation of $\Delta_{s}(G)$ for some suitable choice of start vertex $s$.
We do so in what follows for $s=c$.

Our algorithm goes as follows:

  * •

We compute the equivalence classes $C_{1},C_{2},\ldots,C_{p}$ of $\sim^{c}$.

  * •

For every $1\leq j\leq p$, let $Lab(C_{j})=\\{i\mid 1\leq i\leq t,\
N[P_{i}]\cap C_{j}\neq\emptyset\\}$.

  * •

We output $\Delta^{*}:=\max_{1\leq j\leq t}\max\\{2d(v,P_{i})+2\mid v\in
C_{j},\ i\in Lab(C_{j})\\}$.

Correctness. We prove in what follows that we have
$\Delta^{*}/2-2\leq\Delta_{c}(G)\leq\Delta^{*}$.

First, we pick some class $C_{j}$, for $1\leq j\leq p$, such that
$\max\\{d(v,P_{i})\mid v\in C_{j},\ i\in Lab(C_{j})\\}$ is maximized. By the
maximality of $C_{j}$, we have $\Delta^{*}=2\times\max\\{d(v,P_{i})\mid v\in
C_{j},\ i\in Lab(C_{j})\\}+2$. Let $v\in C_{j}$ and $i\in Lab(C_{j})$ be
maximizing $d(v,P_{i})$. By construction, there exists a vertex $u\in
C_{j}\cap N[P_{i}]$. Then, $\Delta_{c}(G)\geq d(u,v)\geq
d(v,P_{i})-1=\Delta^{*}/2-2$.

Second, we pick some class $C_{j^{\prime}}$, for $1\leq j^{\prime}\leq p$,
such that $\max\\{d(u,v)\mid u,v\in C_{j^{\prime}}\\}$ is maximized. By the
maximality of $C_{j^{\prime}}$, we have $\Delta_{c}(G)=\max\\{d(u,v)\mid
u,v\in C_{j^{\prime}}\\}$. Let $u,v\in C_{j^{\prime}}$ be maximizing $d(u,v)$.
We pick an arbitrary label $i$, for some $1\leq i\leq t$, such that $u\in
N[P_{i}]$ (such a label always exists because $H=\bigcup_{i=1}^{t}P_{i}$ is a
dominating set). In particular, we have $i\in Lab(C_{j^{\prime}})$. Now, let
$x,y\in P_{i}$ satisfy $d(v,x)=d(v,P_{i})$ and $y\in N[u]$. Note that
$|d(c,x)-d(c,v)|\leq d(v,P_{i})$ and that $|d(c,u)-d(c,y)|\leq 1$. As a
result,

$\displaystyle\Delta_{c}(G)$ $\displaystyle=d(u,v)\leq d(v,P_{i})+d(x,y)+1$
$\displaystyle=d(v,P_{i})+|d(c,x)-d(c,y)|+1$ $\displaystyle\leq
d(v,P_{i})+|d(c,x)-d(c,v)|+|d(c,v)-d(c,y)|+1$ $\displaystyle\leq
d(v,P_{i})+|d(c,x)-d(c,v)|+|d(c,u)-d(c,y)|+1$ $\displaystyle\leq
2d(v,P_{i})+2\leq\Delta^{*}.$

Complexity. The equivalence classes of $\sim^{c}$ can be computed in linear
time [14]. In order to compute the label-sets
$Lab(C_{1}),Lab(C_{2}),\ldots,Lab(C_{p})$, we proceed as follows:

  * •

We set $Lab(v):=\emptyset$ for every vertex $v$.

  * •

We scan each shortest path $P_{i}$, for $1\leq i\leq t$, sequentially. For
each vertex $v\in V(P_{i})$, for each vertex $u\in N[v]$, we add label $i$ to
$Lab(u)$.

  * •

For every $1\leq j\leq p$, we set $Lab(C_{j}):=\bigcup_{v\in C_{j}}Lab(v)$.

The runtime of this above procedure is in ${\cal O}(tm+tn)={\cal O}(\alpha
m)$.

Then, for every fixed $P_{i}$, $1\leq i\leq t$, a standard modification of BFS
allows us to compute all distances $d(v,P_{i}),\ v\in V$ in linear time. In
particular, the total runtime in order to compute all distances $d(v,P_{i})$,
for $v\in V$ and $1\leq i\leq t$, is in ${\cal O}(tm)={\cal O}(\alpha m)$.
Now, for every $1\leq j\leq p$, we can compute $\max\\{d(v,P_{i})\mid v\in
C_{j},\ i\in Lab(C_{j})\\}$ in ${\cal O}(t|C_{j}|)={\cal O}(\alpha|C_{j}|)$
time. Recall that $\sum_{j=1}^{p}|C_{j}|=n$. Overall, the total runtime of the
algorithm is in ${\cal O}(\alpha m)$.


# Line-Constrained $k$-Semi-Obnoxious Facility Location

Vishwanath R. Singireddy1 Manjanna Basappa1 The authors, M. Basappa and N. R.
Aravind, were partially supported by SERB TARE Grant TAR/2022/000397. N. R.
Aravind${}^{2\hskip 0.85358pt*}$

( 1BITS Pilani, Hyderabad Campus, India
{p20190420<EMAIL_ADDRESS>
2IIT Hyderabad, India
<EMAIL_ADDRESS>
)

###### Abstract

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}$, …,
$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}^{k}d_{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^{4}k^{2})$ time. Subsequently, we improve the running
time to $O(n^{3}k\cdot\max{(n,k)})$. Furthermore, we addressed two special
cases of the problem where points do not have arbitrary weights. In the first
case, the objective is to encompass the maximum number of blue points while
avoiding red points. The second case aims to encompass all the blue points
with the minimum number of red points covered. We show that these two special
cases can be solved in $O(n^{3}k\cdot\max{(\log{n},k)})$ time. For the first
case, when $k=1$, we also provide an algorithm that solves the problem in
$O(n^{3})$ time, and subsequently, we improve this result to
$O(n^{2}\log{n})$. For the latter case, we give $O(n\log{n})$ time algorithm
that uses the farthest point Voronoi diagram. 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 consider a generalization
of the weighted problem where we are given $t$ horizontal lines instead of one
line. We give an $O(n^{4}k^{2}t^{5})$ time algorithm for this problem.
Finally, we consider a discrete variant where a set of $s$ candidate sites (in
convex position) for placing $k$ facilities is pre-given ($k<s$). We propose
an algorithm that runs in $O(n^{2}s^{2}+ns^{5}k^{2})$ time for this discrete
variant.

Keywords: Semi-obnoxious Facility Location, Complete Weighted Directed Acyclic
Graph, Minimum-weight $k$-link Path, Concave Monge Property, Farthest-point
Voronoi Diagram, Delaunay Triangulation, Dynamic Programming

##  1 Introduction

Given a set $\cal B$ of blue points and a set $\cal R$ of red points above a
horizontal line $\ell$, each point $p_{i}\in{\cal B}\cup{\cal R}$ has a weight
$w_{i}>0$ if $p_{i}\in{\cal B}$ and $w_{i}<0$ if $p_{i}\in R$. Let $|{\cal
B}\cup{\cal R}|=n$, and let $d^{0}$ denote the interior of any geometric
object $d$, i.e., $d^{0}=d\backslash{\partial d}$ where $\partial d$ denotes
the boundary of $d$. The objective is to pack $k$ non-overlapping congruent
disks $d_{1},d_{2},\dots,d_{k}$ of minimum radius, centered on $\ell$, such
that $\sum\limits_{j=1}^{k}\sum\limits_{i\in[n]:\exists p_{i}\in{\cal
R},p_{i}\in d^{0}_{j}}w_{i}+\sum\limits_{j=1}^{k}\sum\limits_{i\in[n]:\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_{j=1}^{k}d_{j}$ is maximized. We
name this problem a Constrained Semi-Obnoxious Facility Location (CSofl)
problem on a Line.

Typically, facility location problems involve two types of facilities:
desirable ones like hospitals, fire stations, and post offices that should be
located as close as possible to demand points (population centers), and
undesirable ones like chemical factories, nuclear plants, and dumping yards
that should be located as far away as possible from demand points to minimize
their negative impact. However, the semi-obnoxious facility location (Sofl)
problems have the unified objective of optimizing both negative and positive
impacts on the repelling and attractive demand sites, respectively. In Sofl
problems, the aim is to locate facilities at an optimal distance from both
attractive and repulsive demand points. This creates a bi-objective problem
where two objectives must be balanced. For example, when building an airport,
it should be located far enough from the city to avoid noise pollution but
close enough to customers to minimize transportation costs.

In [14], the semi-obnoxious facility location problem is modeled as Weber’s
problem, where the repulsive points are assigned with negative weights. This
problem is solved by designing a branch and bound method with the help of
rectangular subdivisions [14]. The problem of locating multiple capacitated
semi-obnoxious facility location problem is solved using a bi-objective
evolutionary strategy algorithm where the objective is to minimize both non-
social and social costs [20]. The problem of locating a single semi-obnoxious
facility within a bounded region is studied by constructing efficient sets
(the endpoints of the efficient segments) [15]. A bi-objective mixed integer
linear programming formulation was introduced and applied to this semi-
obnoxious facility location problem [8].

Golpayegani et al. [12] introduced a semi-obnoxious median line problem in the
plane using Euclidean norm and proposed a particle swarm optimization
algorithm. Later, Golpayegani et al. [13] proposed a particle swarm
optimization that solved the rectilinear case of the semi-obnoxious median
line problem. Recently, Gholami and Fathali [11] solved the circular semi-
obnoxious facility location problem in the Euclidean plane using a cuckoo
optimization algorithm which is known to be a meta-heuristic method. The
problem of locating a single semi-obnoxious facility within a bounded region
is studied by constructing efficient sets. Wagner [21] gave duality results in
his thesis for a non-convex single semi-obnoxious facility location problem in
the Euclidean space. Singireddy and Basappa [18, 19] studied the $k$ obnoxious
facility location problem restricted to a line segment. They initially
proposed an $(1-\epsilon)$-approximation algorithm [18], and then two exact
algorithms based on two different approaches that run in $O((nk)^{2})$ and
$O((n+k)^{2})$ time, respectively, for any $k>0$ and finally, an $O(n\log{n})$
time algorithm for $k=2$ [19]. In [18], they also examined the weighted
variant of the problem (where the influencing range of obnoxious facilities is
fixed and demand points are weighted). They gave a dynamic programming-based
solution that runs in $O(n^{3}k)$ time for this variant. Subsequently, Zhang
[22] refined this result to $O(nk\alpha(nk)\log^{3}{nk})$ by reducing the
problem to the $k$-link shortest path problem on a complete, weighted directed
acyclic graph whose edge weights satisfy the convex Monge property, where
$\alpha(\cdot)$ refers to the inverse Ackermann function. Section 4 of this
paper follows a similar strategy of reducing the weighted CSofl to the
$k$-link path problem, but the edge weights satisfy the concave Monge
property.

The Sofl problem is also closer to the class of geometric separability
problems, where we need to separate the given two sets of points with a linear
or non-linear boundary or surface in a high-dimensional space. Geometric
separability is an important concept in machine learning and pattern
recognition. It is used to determine whether a set of data can be classified
into distinct categories (say, good and bad points type) using a specific
algorithm or model. Then, given an arbitrary data point, we can predict
whether this point is good or bad depending on which side of the separation
boundary hyperplane it falls. O’Rourke et al. [17] gave a linear time
algorithm based on linear programming to check whether a circular separation
exists. They also showed that the smallest disk and the largest separating
circle could be found in $O(n)$ and $O(n\log{n})$ time, respectively. If a
convex polygon with $k$ sides separation exists, then for $k=\Theta(n)$, the
lower bound for computing the minimum enclosing convex polygon with $k$ sides
is $\Omega(n\log{n})$ [9] and can be solved in $O(nk)$ time. While the
separability problem using a simple polygon [10] was shown to be NP-hard,
Mitchell [16] gave $(\log{n})$-approximation algorithm for an arbitrary simple
polygon. Recently, Abidha and Ashok [1] have explored the geometric
separability problems by examining rectangular annuli with fixed (the axis-
aligned) and arbitrary orientation, square annuli with a fixed orientation,
and an orthogonal convex polygon. For rectangular annuli with a fixed
orientation, they gave $O(n\log{n})$ time algorithm. They gave
$O(n^{2}\log{n})$ time algorithm for cases with arbitrary orientation. For a
fixed square case, the running time of their algorithm is $O(n\log^{2}{n})$,
while for the orthogonal convex polygonal cases, it is $O(n\log{n})$ time.

##  2 Preliminaries

This section briefly introduces various notations and definitions that will be
used in further sections.

Let ${\cal L}_{\textsc{can}}$ denote the set of candidate radii and
$r_{\textsc{can}}\in{\cal L}_{\textsc{can}}$ a candidate radius. The optimal
radius is denoted as $r_{opt}$. Let $dist(u,v)$ denote the minimum Euclidean
distance between two points $u$ and $v$. Given a graph $G(V,E)$, the weight of
an edge is denoted as $w(i,j)$ where $\overline{ij}\in E$. The path between
any two vertices $v,u\in V$ is denoted as $\Pi(v,u)$.

######  Definition 1.

Configurations: Arrangement of $k$-disks in any feasible solution to the CSofl
problem with different placements of red and blue points on the boundaries of
the disks (critical regions). A configuration is said to be critical if it
corresponds to some candidate radius $r_{\textsc{can}}\in{\cal
L}_{\textsc{can}}$.

######  Definition 2.

DAG: It stands for Directed Acyclic Graph. It is a directed graph that has no
directed cycles. In other words, it is a graph consisting of a set of nodes
connected by directed edges, where the edges have a specific direction. There
is no way to start at any node and follow a sequence of edges that eventually
loops back to that node.

######  Definition 3.

The minimum weight $k$-link path: Given a complete weighted DAG $G(V,E)$, and
two vertices $s$ (source) and $t$ (target), the minimum weight $k$-link path
problem seeks to find a minimum weight path from $s$ to $t$ such that the path
has exactly $k$ edges (links) in it.

######  Definition 4.

Concave Monge property: The weight function $w$ for a given weighted, complete
DAG $G(V,E)$ satisfies the concave Monge property if for all $i,j\in V$ we
have the inequality $w(i,j)+w(i+1,j+1)\leq w(i,j+1)+w(i+1,j)$ satisfied, where
$1<i+1<j<n$.

The outline of the algorithm for the CSofl problem is as follows:

  1. 1.

First, all possible configurations of the $k$ disks and red and blue points in
any feasible solution to the CSofl problem are identified. We show that a
finite number of distinct configurations exist, and there are specifically
$O(1)$ distinct critical-configuration types.

  2. 2.

The next step entails computing all possible candidate radii, ${\cal
L}_{\textsc{can}}$, where we have one ${r}_{\textsc{can}}$ corresponding to
each of the configurations identified in the previous step.

  3. 3.

After obtaining a candidate radius $r_{\textsc{can}}$, the given instance of
the CSofl problem will be transformed into an instance of the problem of
computing a minimum weight $k$-link path problem on a complete weighted DAG
$G$.

  4. 4.

The semi-obnoxious facilities (disks) should then be positioned (i.e., the
centers of these disks are to be positioned) at the points on $\ell$
corresponding to vertices of the aforementioned minimum weight $k$-link path
$\Pi_{k}^{*}(s,t)$ in $G$. The total weight of the points covered by these
facilities can be computed using the $\Pi_{k}^{*}(s,t)$ weight.

  5. 5.

To determine the set of all radii ${\cal
L_{\textsc{can}}}=\\{\lambda_{1},\lambda_{2},\dots\\}$ for which the total
weight of the covered points is the largest, the above process must be
repeated for every candidate radius $r_{\textsc{can}}$.

  6. 6.

Finally, the locations of the $k$ semi-obnoxious facilities placed with the
smallest $\lambda\in{\cal L}_{\textsc{can}}$ and covering the points with the
largest total weight is returned as the output.

##  3 Computing the candidate radii

In this section, we find all the candidate radii by considering all
configurations involving disks as well as blue and red points.

  * Configuration-0:

Suppose that all the red points lie closer to $\ell$ than the blue points and
have significantly more negative weights than the blue points (see Figure 1).
In this scenario, covering any blue points would also cover some red points
since the disks must be centered on $\ell$. This, in turn, would result in a
negative total weight. As a result, we can opt to keep zero-radius disks that
do not cover any points rather than covering any of the blue points. This way,
the maximum weight will be zero. It also implies the following observation.

######  Observation 1.

An optimal (feasible) solution always exists for any given problem instance.

Figure 1: Configuration-0.

  * Configuration-1:

We consider a specific configuration in which the radius of the disks in the
optimal solution is determined by only one blue point. As shown in Figure 2,
we can observe that the disks $d_{i}$ and $d_{i+1}$, which have one blue point
on each of their boundaries, will have a smaller (optimal) radius compared to
the dotted disk $d_{i}^{\prime}$, which also covers the same blue points. This
is because our problem is to find the minimum radius disks that cover the
maximum weight.

Figure 2: Configuration-1.

Here, we consider at least one of the blue points lying on the boundary of at
least one of the $k$ disks, which determines the radius of the disks in the
optimal solution for a radius greater than zero. Observe that the radius of
the disk is the $y$-coordinate value of the point that lies on the disk
boundary. Hence, we add $O(n)$ candidate radii to ${\cal L}_{\textsc{can}}$
and the radii are $r_{\textsc{can}}=y_{p_{i}}$, where $y_{p_{i}}$ denotes the
$y$-coordinate of the point $p_{i}$ for each $p_{i}\in{\cal B}$,
$i=1,2,\dots,n$.

  * Configuration-2:

In this scenario, we consider the case where the optimal solution is
determined by two points on the boundary of at least one of the $k$ disks,
which can either be two blue points or one blue and one red point. We notice
that no two red points on any disk’s boundary will determine the disk’s
radius, as we can further reduce the disk’s radius until its boundary touches
at least one of the blue points. To calculate the candidate radii for the
disks, we proceed as follows:

Consider a point $p_{i}\in{\cal B}$ and a point $p_{j}\in{\cal R}$. If they
determine the minimum radius of the disks in a solution to CSofl problem, then
the candidate radius $r_{\textsc{can}}$ can be computed by drawing a bisector
line $\ell_{i,j}$ until $\ell_{i,j}$ cuts across $\ell$ where $p_{i}$ is in
the counter-clockwise direction from $\ell_{i,j}$ and $p_{j}$ in the clockwise
direction from $\ell_{i,j}$ (see Figure 3).

Figure 3: Illustration of calculating $r_{\textsc{can}}$.

Let $(x_{p_{i},p_{j}},y_{p_{i},p_{j}})$ be the center of the disk,
$(x_{p_{i}},y_{p_{i}})$ and $(x_{p_{j}},y_{p_{j}})$ are the coordinates of the
points $p_{i}$ and $p_{j}$ respectively. Then, we have

$(x_{p_{i}}-x_{p_{i},p_{j}})^{2}+(y_{p_{i}}-y_{p_{i},p_{j}})^{2}=(x_{p_{j}}-x_{p_{i},p_{j}})^{2}+(y_{p_{j}}-y_{p_{i},p_{j}})^{2}$

After simplification, we have
$r_{\textsc{can}}=\sqrt{(x_{p_{i}}-x_{p_{i},p_{j}})^{2}+y_{p_{i}}^{2}}$ for
the two cases:

    * –

$p_{i}\in{\cal B}$ and $p_{j}\in{\cal R}$.

    * –

$p_{i},p_{j}\in{\cal B}$.

where
$x_{p_{i},p_{j}}=\frac{(y_{p_{j}}-y_{p_{i}})(y_{p_{j}}+y_{p_{i}})}{2(x_{p_{j}}-x_{p_{i}})}+\frac{(x_{p_{j}}+x_{p_{i}})}{2}$,
$y_{p_{i},p_{j}}=0$. Here, as we consider a candidate radius for every pair of
points except the red-red pair, we add $O(n^{2})$ candidate radii to ${\cal
L}_{\textsc{can}}$ for this critical-configuration type.

######  Observation 2.

There are only $O(1)$ critical configuration types.

###### Proof.

In any of the optimal placements of the disks, either one blue point or a pair
of blue points, or a pair of red and blue points will determine the disk’s
radius. Even though there may be more than two points lying on the boundary of
the disks in any optimal packing, only two points among them will determine
the radius of the disk since there exists a unique disk that passes through
two points and is centered on $\ell$. Hence, any configurations of points
lying on the boundary of the disk can be transformed into any of the above-
mentioned configurations by perturbing the center or reducing the radius of
the disks. Therefore, we have a constant number of critical configuration
types, namely, four types, including the configuration-0. ∎

######  Lemma 1.

$|{\cal L}_{\textsc{can}}|=O(n^{2})$.

###### Proof.

It follows from Observation 2 since a constant number of critical
configuration types (viz. no points, one blue point, a pair of blue points,
and a pair of blue and red points) contribute to the candidate radii. In any
of the configurations, at most, two points will determine the radius of the
disks. Hence we have $O(n^{2})$ candidate radii corresponding to that
configuration. Thus, the lemma follows. ∎

##  4 Transformation to the minimum weight $k$-link path problem

In this section, we demonstrate that the CSofl problem can be reduced to the
problem of computing a minimum weight $k$-link path between a pair of vertices
in a weighted DAG $G(V,E)$. Each edge $\overline{ij}\in E$ in $G$ is assigned
a weight $w:(i,j)\rightarrow\mathbb{R}$ that is either a positive or negative
real number $w(i,j)\in\mathbb{R}$.

The minimum weight $k$-link path $\Pi(s,t)$ is a path from the source $s$ to
the target vertex $t$, consisting of exactly $k$ edges, and has the minimum
total weight among all $k$-link paths between $s$ and $t$, where the weight of
a $k$-link path is the sum of weights of the edges in the path, i.e.,

$w(\Pi(s\rightarrow i_{1}\rightarrow i_{2}\rightarrow\dots\rightarrow
i_{k-1}\rightarrow
t))=\sum\limits_{j=1}^{k-2}w(i_{j},i_{j+1})+w(s,i_{1})+w(i_{k-1},t)$

Let $\lambda=r_{\textsc{can}}$. Next, we transform an instance of the CSofl
problem to an instance of $k$-link path problem on a DAG $G(V,E)$ as follows:

Let us call the maximal interval $f_{i}^{+}=[l_{i},r_{i}]$ on $\ell$ as the
influence interval (within which a facility or a disk with radius
$r_{\textsc{can}}$ centered will influence or cover the point $p_{i}$) for the
point $p_{i}\in{\cal B}$ if the distance between any point on $[l_{i},r_{i}]$
and $p_{i}$ is at most $r_{\textsc{can}}$. Similarly,
$f_{i}^{-}=[l_{i},r_{i}]$ is the influence interval on $\ell$ for
$p_{i}\in{\cal R}$.

Let the set of all influence intervals be $F=\\{f_{i}^{+}\mid
i\in[n],p_{i}\in{\cal B}\\}\cup\\{f_{i}^{-}\mid i\in[n],p_{i}\in{\cal R}\\}$.
Let the vertex set $V=\\{l_{1},r_{1},l_{2},r_{2},\dots,l_{n},r_{n}\\}$ be the
end points of the intervals in $F$. For each $l_{i},i\in[n]$, we also add
$2(k-1)$ extra vertices corresponding to points on $\ell$ at distance
$l_{i}+2\lambda,l_{i}+4\lambda,\dots,l_{i}+2(k-1)\lambda,l_{i}-2\lambda,l_{i}-4\lambda,\dots,l_{i}-2(k-1)\lambda$,
to $V$. Similarly, we add $2(k-1)$ vertices for every $r_{i},i\in[n]$, placed
at points at distance
$r_{i}-2\lambda,r_{i}-4\lambda,\dots,r_{i}-2(k-1)\lambda,r_{i}+2\lambda,r_{i}+4\lambda,\dots,r_{i}-2(k-1)\lambda$.
The addition of these extra $2(k-1)$ points on the sides of both endpoints of
each influence interval is because it is possible to have disks centered at
points on $\ell$ other than the endpoints of influence intervals in an optimal
solution (see Figure 4 for an illustration). However, at least one disk must
be centered at an endpoint in any optimal solution. In Figure 4, we can
observe that the disks $d_{i-1}$ and $d_{i+1}$ are not centered at any
endpoint of the intervals in $F$ since none of the points in ${\cal
B}\cup{\cal R}$ lie on their boundary.

Figure 4: An optimal packing of $3$ disks for a candidate radius $\lambda$,
$d_{i}$ is centered at an endpoint of the influence interval due to $p_{i}$.

Without loss of generality, the vertices may be relabeled as
$V=\\{v_{1},v_{2},\dots,v_{m}\\}$ based on the increasing order of
$x$-coordinates of all $l_{i}$ and $r_{i}$ for $i\in[n]$, and the extra added
points, where $m=O(kn)$. Furthermore, we can update $V$ so that all the
corresponding points in $V$ have distinct $x$-coordinates. Let $s$ and $t$ be
the points placed on $\ell$ at a distance of $2k\lambda$ from the left
endpoint of the leftmost interval $l_{1}$ and from the right endpoint of the
rightmost interval $r_{\textsc{l}}$, respectively, where
$[l_{\textsc{l}},r_{\textsc{l}}]$ denotes the rightmost influence interval
(see Figure 5). Note that $s$ lies on the left of all the points in $V$, and
$t$ lies on the right of all the points in $V$.

Figure 5: Adding of extra-points including $s$ and $t$. Figure 6: Calculation
of the weight of an edge.

Let $w(d_{i})$ denote the total weight of the points covered by the disk with
radius $\lambda$ centered at $c_{i}\in V$. We calculate $w(d_{i})$ for the
disks centered at each point $c_{i}\in V$.

Now, the weight of an edge $\overline{ij}\in E$ is calculated as follows:

  * •

$w(i,j)=+\infty$ if the $dist(i,j)<2\lambda$.

  * •

$w(i,j)=-(w(d_{i})+w(d_{j}))$ if $dist(i,j)\geq 2\lambda$ for all $i,j\in V$,
i.e., we add a directed edge between every pair of vertices $i,j\in V$
($i<j$), if the distance between them is at least $2\lambda$ and we add the
corresponding weights (see Figure 6) and negate it.

  * •

Clearly observe that $w(d_{s})$ and $w(d_{t})$ is zero. It is also zero for
the disks centered at first (at most) $k-1$ and last (at most) $k-1$ points
(since they are the points on $\ell$ which are separated by a distance of at
least $2\lambda$ on the left of $l_{1}$ and the right of $r_{\textsc{l}}$),
respectively for every endpoint of the influence interval.

Without loss of generality, let $G^{\prime}(V^{\prime},E^{\prime})$ be the
graph obtained by the above transformation. There will be $O(nk)$ vertices in
$V^{\prime}$, and a directed edge from $i$ to $j$ for all $i,j\in V^{\prime}$
such that $i<j$. Then, $G^{\prime}$ is a complete DAG with
$|V^{\prime}|=O(nk)$ vertices and $|E^{\prime}|=O(n^{2}k^{2})$ edges, and
every edge $(i,j)\in E^{\prime}$ is assigned a weight as discussed above.
Hence, we have the following lemma.

######  Lemma 2.

The graph $G^{\prime}$ can be constructed in $O(n^{2}k^{2})$ time.

###### Proof.

We start by considering the way we constructed $G^{\prime}$. Every demand
point $p_{i}\in{\cal B}\cup{\cal R}$ can contribute at most two endpoints of
an interval on $\ell$ at a distance of $2\lambda$ from each other. If we
center a disk on that interval, the demand points will either lie on the
boundary or the interior of the disk. Next, we add $2(k-1)$ points on both
sides of each endpoint on $\ell$ with a separation distance of $2\lambda$
between any two consecutive of them. Thus, we have a total of $O(nk)$ points
on $\ell$, which includes $s$ and $t$ and are added to $V^{\prime}$. Now, from
every point in $V^{\prime}$, we add a weighted directed edge to all the points
of $V^{\prime}$ that lie on the right of that point on $\ell$. This will
result in a total of $O(n^{2}k^{2})$ edges, where each edge is assigned a
corresponding weight, as discussed earlier. Therefore, the resulting graph
$G^{\prime}(V^{\prime},E^{\prime})$ has $O(nk)$ vertices, $O(n^{2}k^{2})$
edges, and can be constructed in $O(n^{2}k^{2})$ time. ∎

The edge weights of $G^{\prime}$ will satisfy the concave Monge property for
any four vertices $i,i+1,j,j+1$ of $G^{\prime}$ such that $i<i+1<j<j+1$, the
weights of the directed edges from $i$ to $j$ and from $i+1$ to $j+1$ are not
greater than the weights of the directed edges from $i$ to $j+1$ and from
$i+1$ to $j$.

######  Observation 3.

The edge weights of $G^{\prime}$ satisfy the concave Monge property.

###### Proof.

Figure 7: Any four vertices of $G^{\prime}$ that satisfy the concave Monge
property.

Recall the definition of the concave Monge property, i.e.,
$w(i,j)+w(i+1,j+1)\leq w(i,j+1)+w(i+1,j)$ (see Figure 7). The weights assigned
to the edges of $G^{\prime}$ are assigned based on the following two rules:

  1. 1.

$w(i,j)=+\infty$ if the $dist(i,j)<2\lambda$.

  2. 2.

$w(i,j)=-(w(d_{i})+w(d_{j}))$ if $dist(i,j)\geq 2\lambda$ for all $i,j\in V$

Suppose we select any four vertices with their index labels satisfying
$i<i+1<j<j+1$ in $G^{\prime}$ such that the distance between them is at least
$2\lambda$. Then, according to rule 2, the corresponding weights assigned to
the edges satisfy $w(i,j)+w(i+1,j+1)=w(i,j+1)+w(i+1,j)$. Now, consider another
set of four vertices $i<i+1<j<j+1$ in $G^{\prime}$ such that the distance
between the two closest points among them is less than $2\lambda$, i.e.,
$dist(i+1,j)<2\lambda$. According to rule 1, the corresponding weight assigned
to the edges between these vertices is $+\infty$. Then, we have
$w(i,j)+w(i+1,j+1)<w(i,j+1)+w(i+1,j)$, which satisfies the concave Monge
property. Finally, suppose all four selected vertices $i<i+1<j<j+1$ in
$G^{\prime}$ have a distance between any two consecutive of them less than
$2\lambda$. In this case, according to rule 1, the weights assigned to the
corresponding edges satisfy $w(i,j)+w(i+1,j+1)=w(i,j+1)+w(i+1,j)$.

Therefore, we have shown that if we select any four vertices $i<i+1<j<j+1$ in
$G^{\prime}$, the weights of all these edges satisfy the concave Monge
property. Thus, the observation follows. ∎

Since the constructed graph $G^{\prime}$ is a weighted complete DAG and its
edge weights satisfy the concave Monge property, we have the following theorem
for finding the minimum weight $(k+1)$-link path between any pair of vertices
of $G^{\prime}$.

######  Theorem 1.

[2] The minimum weight $(k+1)$-link path $\Pi_{(k+1)}^{*}(s,t)$ in
$G^{\prime}$ can be computed in $O(nk\sqrt{k\log{(nk)}})$ time.

######  Theorem 2.

We can solve the CSofl problem in polynomial time.

###### Proof.

It follows from Lemma 1, Lemma 2 and Theorem 1. The running time of the
algorithm is
$n^{2}\cdot(O(n^{2}k^{2})+O(nk\sqrt{k\log{(nk)}}))=O(n^{4}k^{2})$. The
algorithm will return the minimum $r_{\textsc{can}}=r_{opt}$, corresponding to
which the computed $(k+1)$-link path between $s$ and $t$ has the minimum total
weight $w(\Pi_{(k+1)}^{*}(s,t))$. The disks with radius $r_{opt}$ can be
centered at $k$ internal vertices of the $(k+1)$-link path (excluding the
terminal vertices $s$ and $t$). The total weight is $\sum_{i\in
Sol}w(d_{i})=-w(\Pi_{(k+1)}^{*}(s,t))/2$, where $d_{i}$ is a disk centered at
$i$ having radius $r_{opt}$ and
$Sol=V(\Pi_{(k+1)}^{*}(s,t))\setminus\\{s,t\\}$ is the set of vertices (the
corresponding points on $\ell$) of $(k+1)$-link path except $s$ and $t$. ∎

Improvement: Recall that the points corresponding to the vertices in
$V^{\prime}$ are labeled as $1,2,\ldots,m$, where $m=O(nk)$. Here, we show
that we can improve the runtime of Theorem 2 (by almost linear factor) by not
explicitly constructing the complete graph $G^{\prime}$. As we have seen in
the proof of Lemma 2, this construction requires $O(n^{2}k^{2})$ time for each
of $O(n^{2})$ candidate radius. However, for every candidate radius
$r_{\textsc{can}}$, we need to precompute the two arrays $w[]$ and $p[]$, each
of size $O(nk)$. Here, $w[i]$ stores the sum of weights of the demand points
covered by the disk of radius $r_{\textsc{can}}$ centered at a point labeled
$i\in V^{\prime}$ on $\ell$, for each $i\in[m]$. The element $p[i]$ stores the
index $i^{\prime}\in V^{\prime}$ of the rightmost point at a distance of at
least $2\lambda$ from $i$ such that $i^{\prime}<i$. We now give a dynamic
program algorithm to compute the maximum weight of a $(k+1)$-link path from
point $1$ to point $m$ (here, the points labeled $1$ and $m$ are the vertices
$s$ and $t$ respectively, in $G^{\prime}$). For a pair of points $i,j$ ($i<j$)
on $\ell$; we redefine the weight of the edge $(i,j)$ to be equal to $w(j)$ as
we need not negate the sum of weights and construct the whole directed graph .

We define the subproblem $\phi(i,j)$ as the problem of finding the maximum
weight $j$-link path in the subgraph $G^{\prime}_{i}$ induced by the vertices
$1,2,\dots,i$. That is,
$\phi(i,j)=\max\limits_{i^{\prime}}\\{w(\Pi_{j}(1,i^{\prime}))\\}$, where
$(j+1)\leq i^{\prime}\leq i$. Then we have the following recurrence:

$\phi(i,j)=\max\\{\phi(i-1,j),\phi(p[i],j-1)+w[i]\\}$ (1)

As $i=1,2,\dots,O(nk)$, and $j=1,2,\dots,k+1$, there are $nk\cdot k=O(nk^{2})$
entries in the DP table table $\phi(i,j)$, each requiring $O(1)$ time to
compute.

Hence, for a given $r_{\textsc{can}}$, the bottom-up implementation of the
above dynamic programming algorithm takes time $O(nk^{2})$ provided that we
have the entries $w[i]$ and $p[i]$ precomputed for each $i\in[m]$.

######  Theorem 3.

The above-improved algorithm for the CSofl problem has the time complexity of
$O(n^{3}k\cdot\max{(n,k)})$.

###### Proof.

The proof is as follows:

  * •

There are $O(n^{2})$ candidate radii in ${\cal L}_{\textsc{can}}$.

  * •

For each candidate radius $\lambda\in{\cal L}_{\textsc{can}}$, we find $O(nk)$
points on $\ell$ as discussed above.

  * •

To compute the weight $w[i]$ of each point $i\in V^{\prime}$ on $\ell$, we
answer a circular range reporting query [6], which takes $O(\log n+\kappa)$
time for a query circle centered at each of $O(nk)$ points on $\ell$, where
$\kappa$ is the number of points reported. It has a preprocessing time of
$O(n\log{n})$ and requires $O(n)$ space.

  * •

For each $\lambda\in{\cal L}_{\textsc{can}}$, the above dynamic programming
algorithm will take $O(nk^{2})$ time. However, the bottleneck in computing the
optimal value $\phi(m,k+1)$ is in computing the arrays $w[]$ for each of
$O(n^{2})$ candidate radius. The total time for computing this array is
$n\log{n}+\sum\limits_{j=1}^{|{\cal
L}_{\textsc{can}}|}(\sum\limits_{i=1}^{m}(\log{n}+\kappa_{i}))$, where
$\kappa_{i}$ is the number of points reported by the query algorithm for a
given query disk centered at $i\in[m]$, where $m=O(nk)$. We see that
$\sum\limits_{j=1}^{|{\cal
L}_{\textsc{can}}|}(\sum\limits_{i=1}^{m}(\log{n}+\kappa_{i}))=n^{3}k\log{n}+\sum\limits_{j=1}^{|{\cal
L}_{\textsc{can}}|}n\chi$, where
$\chi=\max\\{\chi_{1},\chi_{2},\ldots,\chi_{O(n^{2})}\\}$, and $\chi_{j}$ is
the ply111The ply of a set $P$ of points with respect to a set $D$ of disks
$d_{1},d_{2},\ldots,$ is the largest number of those disks in
$\bigcup_{i=1,2.\ldots}d_{i}$ whose intersection contains a point $p\in P$. of
the pointset ${\cal B}\bigcup{\cal R}$ with respect to the set of all disks
$i\in[m]$ for a candidate radius $\lambda_{j}\in{\cal L}_{\textsc{can}}$.
Observe that the ply of ${\cal B}\bigcup{\cal R}$ for a given set of $O(nk)$
disks is $O(n)$ only since a point from ${\cal B}\bigcup{\cal R}$ lying in a
disk centered at an endpoint $i$ of influence interval can not be contained
inside the $2(k-1)$ disks centered at distances
$l_{i}+2\lambda,l_{i}+4\lambda,\dots,l_{i}+2(k-1)\lambda,l_{i}-2\lambda,l_{i}-4\lambda,\dots,l_{i}-2(k-1)\lambda$.
Therefore, $\sum\limits_{j=1}^{|{\cal
L}_{\textsc{can}}|}(\sum\limits_{i=1}^{m}\kappa_{i})\leq\sum\limits_{j=1}^{|{\cal
L}_{\textsc{can}}|}(nk\chi)=O(n^{4}k)$ as $\chi=O(n)$.

  * •

Hence the total running time is
$n^{2}\cdot(O(nk^{2})+O(nk\log{n})+O(n^{2}k))=O(n^{3}k\cdot\max{(n,k)})$.

Now, we prove the correctness of the dynamic programming recurrence relation 1
by inducting on the number of disks placed.

Correctness: Fix a radius $\lambda\in{\cal L}_{\textsc{can}}$. By induction on
$i+j$, we can prove the recurrence relation 1 is correct, as follows. For the
base case $j=1$, $i\geq 2$, we have
$\phi(i,1)=w(\Pi_{1}(1,i))=\max\limits_{2\leq q\leq i}{(w[q])}$, which is the
maximum weight of a 1-link path originating at vertex 1 in the subgraph
$G^{\prime}_{i}$ induced by the vertices $1,2,\dots,i$. This is the optimal
solution for the subproblem $\phi(i,1)$. For the base case $j\geq 2$, $i=2$,
we have that $\phi(i,j)=\phi(i,2)$ as the weight contributed by the remaining
$j-2$ disks centered on $\ell$ is zero.

Let $p[s]=\max\\{q\mid(dist(s,q)\geq 2\lambda,2\leq q<s\\}$ for $2\leq s\leq
i$. Assume that the recurrence relation holds for all subproblems
$\phi(i^{\prime},j^{\prime})$, where $(i^{\prime}+j^{\prime})<(i+j)$. Consider
the subproblem $\phi(i,j)$, and for solving this subproblem, we consider two
cases for the vertex $i$: either $\Pi_{j}(1,i)$ uses vertex $i$ or it doesn’t.

Case $1$: $\Pi_{j}(1,i)$ does not use vertex $i$. In this case, $\Pi_{j}(1,i)$
is also an optimal $j$-link path in $G^{\prime}_{i-1}$ by induction
hypothesis. Therefore, the optimal solution for the subproblem $\phi(i,j)$ is
the same as for the subproblem $\phi(i-1,j)$.

Case $2$: $\Pi_{j}(1,i)$ uses vertex $i$. Let $i^{\prime}=p[i]$, which is the
predecessor of $i$ on $\Pi_{j}(1,i)$. Then, $\Pi_{j}(1,i)$ can be decomposed
into two parts: an optimal $(j-1)$-link path in $G^{\prime}_{i^{\prime}}$ (by
induction hypothesis), denoted by $\Pi_{j-1}(1,i^{\prime})$, and the edge
$(i^{\prime},i)$ with weight $w[i]$. Since $\Pi_{j}(1,i)$ is an optimal path
ending at $i$ in the subgraph $G_{i}^{\prime}$, the weight of $\Pi_{j}(1,i)$
is equal to the sum of the weights of $\Pi_{j-1}(1,i^{\prime})$ and
$(i^{\prime},i)$, i.e., $w(\Pi_{j}(1,i))=w(\Pi_{j-1}(1,i^{\prime}))+w[i]$.

Therefore, the optimal solution for the subproblem $\phi(i,j)$ is the maximum
weight of all $j$-link paths in $G^{\prime}_{i}$. This is achieved by either
taking the optimal solution for the subproblem $\phi(i-1,j)$ or by taking the
optimal solution for the subproblem $\phi(i^{\prime},j-1)$ and adding the
weight of edge $(i^{\prime},i)$, i.e.,
$\phi(i,j)=\max{(\phi(i-1,j),\phi(p[i],j-1)+w[i])}$.

By using the recurrence relation for $\phi(i-1,j)$ and $\phi(p[i],j-1)$, which
can be computed by solving the subproblems $\phi(i-1,j-1)$ and
$\phi(p[i],j-1)$. Therefore, we can use the recurrence relation to obtain the
optimal solution for $\phi(i,j)$.

By the principle of mathematical induction, the recurrence relation holds for
all subproblems $\phi(i,j)$, where $1\leq j\leq k$. Given that we have
precomputed all the values in the arrays $w[]$ and $p[]$, it takes constant
time to compute the optimal solution to each subproblem by combining optimal
solutions to smaller subproblems. Further, we have $O(nk^{2})$ distinct
subproblems in total for the recurrence. Hence, the overall time complexity of
the algorithm is $O(nk^{2})$. ∎

##  5 Special cases of CSofl

In this section, we consider the following two special cases of the CSofl
problem with some specific application.

######  Problem 4.

AllBlue-MinRed: The problem aims to cover all blue points while covering the
minimum number of red points. To solve this problem, we modify the weights of
the demand points as follows: for every point $p_{i}\in{\cal R}$, let
$w_{i}=\delta$ and for every point $p_{i}\in{\cal B}$, the weight
$w_{i}>-|{\cal R}|\delta$, where $\delta\in\mathbb{R}$ is an arbitrary real
value and $\delta<0$.

This problem has some specific applications in defense, as will be discussed:
assuming a scenario where there are two groups of points along a horizontal
line, one represented by blue points (enemy forces) and the other by red
points (civilians), the goal is to determine the center locations and blast
radius required for a fixed number of explosives to target all enemy forces
while isolating the civilians as much as possible. Alternatively, suppose the
scenario is such that the red points represent enemy forces, and the objective
is to establish wireless communication among our own forces (represented by
blue points). In that case, the goal is to place $k$ base stations to cover
all blue forces while minimizing the transmissions intercepted by the red
forces (enemy forces).

######  Problem 5.

MaxBlue-NoRed: In this problem, we need to cover the maximum number of blue
points, and at the same time, none of the red points need to be covered. To
solve this problem, we modify the weights of the demand points as follows: for
every point $p_{i}\in{\cal B}$, let $w_{i}=\delta$, and for every point
$p_{i}\in{\cal R}$, the weight $w_{i}<-|{\cal B}|\delta$, where
$\delta\in\mathbb{R}$ is an arbitrary real value and $\delta>0$.

This problem has the following specific applications: place a set of $k$
sensors on a horizontal line to cover as many blue points as possible while
avoiding red ones. This scenario can arise, for example, in battlefield
surveillance, where the red points represent friendly forces, and the blue
points represent enemy forces. The goal is to deploy sensors to monitor the
enemy forces while avoiding the friendly forces. Similarly, the problem can
arise in wildlife conservation, where the blue points represent areas of high
animal activity, and the red points represent protected or private residential
areas. The goal is to deploy sensors to monitor animal activity while avoiding
private or protected areas.

######  Claim 1.

The algorithm of Theorem 2 will eventually find an optimal solution (i.e.,
selects at most $k$ facility locations on $\ell$ to cover all the blue points)
for the AllBlue-MinRed problem.

###### Proof.

Consider an instance of CSofl with $w_{i}=\delta$ for every $p_{i}\in{\cal R}$
and the weight $w_{i}>-|{\cal R}|\delta$ for every $p_{i}\in{\cal B}$, where
$\delta\in\mathbb{R}$ is an arbitrary negative real value.

Feasibility: The weight assignment of $w_{i}$ ($>-|{\cal R}|\delta$)
guarantees that all blue points will be covered. In the worst-case scenario, a
single disk can cover all points, both blue and red points, whose total weight
is positive due to the weight assignment. The remaining $k-1$ disks can be
centered on $\ell$ to cover none of the points. This ensures that a feasible
solution exists for the AllBlue-MinRed problem.

Optimality: Suppose there is a feasible solution for the CSofl problem that
places at most $k$ facility centers on $\ell$. Let these facilities cover all
points in ${\cal B}$ and some points in ${\cal R}$, with total weight equal to
$\rho$. Now observe that it is impossible to improve the weight $\rho$ to
$\rho^{\prime}$ ($>\rho$) by relocating one of the center locations, which
then uncovers $m^{\prime}$ red points and one blue point (whose weight is,
say, $-|{\cal R}|\delta+\epsilon$ for some $\epsilon>0$). If we do so, then
the updated weight would be $\rho^{\prime}=\rho-m^{\prime}\delta+|{\cal
R}|\delta-\epsilon$. But, $\rho^{\prime}$ is no better than the earlier weight
$\rho$ since $m^{\prime}\leq|{\cal R}|$, $\delta<0$ and
$(-m^{\prime}\delta+|{\cal R}|\delta-\epsilon)<0$. Further, the optimal
solution with total weight $\rho$ for the CSofl (computed by using the
algorithm of Theorem 2) is also optimal for this particular variant since
$\rho$ can not be improved by uncovering only red points. Hence, the above
proposed algorithm for the CSofl problem will also correctly solve the
AllBlue-MinRed problem. ∎

######  Claim 2.

The algorithm of Theorem 2 solves the MaxBlue-NoRed problem optimally.

###### Proof.

Consider an instance of the CSofl problem, in which every $p_{i}\in{\cal B}$
is associated with the weight $w_{i}=\delta$, and every $p_{i}\in{\cal R}$ is
associated with the weight $w_{i}<-|{\cal B}|\delta$, where
$\delta\in\mathbb{R}$ and $\delta>0$.

Feasibility: Consider the following trivial feasible solution for the CSofl
problem. Let us place $k$ facility center locations on $\ell$ so that they
don’t cover any blue points. Further, we reduce their radius so that no red
points lie in the interior. Note that the total weight of the demand points
covered by these facilities is zero. Hence, these $k$ center locations form a
feasible solution for the MaxBlue-NoRed problem since none of the red points
are covered, and the total weight is zero.

Optimality: Suppose we have a feasible solution with a total weight $\rho$ for
the CSofl problem. We will try to increase this weight by relocating one of
the centers covering additional $n^{\prime}$ blue points and (at least) one
red point. The update weight would be
$\rho^{\prime}=\rho+n^{\prime}\delta-|{\cal B}|\delta$ which is smaller than
$\rho$ since $n^{\prime}\leq|{\cal B}|$ and $\delta>0$. Hence, we cannot
improve the total weight by perturbing some centers to cover one more red
point with the hope that it may allow us to cover some more (or even all) blue
points. When we have an optimal solution with the total weight $\rho$ for an
instance of the CSofl problem, the weight the covered blue points contribute
can not be increased due to its optimality. On the other hand, this solution
also can not cover any red point because we can get a better weight
$\rho^{\prime}=\rho-n^{\prime}\delta+|{\cal B}|\delta$ (by reducing the radius
to uncover these red points. While doing so, we possibly uncover some blue
points, say $n^{\prime}$.) This would contradict that $\rho$ is the optimum.
Hence, the above proposed algorithm (of Theorem 2) for the CSofl problem will
also correctly solve the MaxBlue-NoRed problem. ∎

######  Corollary 1.

The AllBlue-MinRed and MaxBlue-NoRed problems can be solved in
$O(n^{3}k\cdot\max{(\log{n},k)})$ time.

###### Proof.

Since there are only two types of weights (namely, $\delta$ and $|{\cal
B}|\delta$ or $-|{\cal R}|\delta$), instead of answering circular range
reporting queries, we answer range counting queries [6], viz. blue count and
red count for each of $O(nk)$ query circles of every candidate radius. Hence
the total running time is
$n^{2}\cdot(O(nk^{2})+O(nk\log{n}))=O(n^{3}k\cdot\max{(\log{n},k)})$. Hence,
the theorem follows from Theorem 2 and Claims 1 and 2. ∎

###  5.1 The MaxBlue-NoRed problem for $k=1$

In this section, we address the problem of determining the minimum enclosing
disk with center on $\ell$, which encloses the maximum number of blue points
without enclosing any red points. Recall that in the MaxBlue-NoRed problem, we
are given two sets of points, blue points ${\cal B}$ and red points ${\cal
R}$, lying above a horizontal line $\ell$, where $|{\cal B}|+|{\cal R}|=n$,
the goal is to compute a minimum enclosing disk that maximizes the count of
blue points (being enclosed in that disk) while ensuring that no red point is
enclosed.

######  Observation 4.

If the perpendicular bisector of any two points $p_{i}$ and $p_{j}$ intersects
$\ell$ at $c_{i}$, then there exists a disk centered at $c_{i}$ which has
$p_{i}$ and $p_{j}$ on its boundary.

The method for solving the problem is as follows:

  * •

For each pair of points in the set ${\cal B}\cup{\cal R}$, compute the
perpendicular bisector of the line segment connecting them. Store the
intersection points of these perpendicular bisectors with the line $\ell$ in a
set $I$. Also, add to the set $I$ all intersection points of $\ell$ with a
vertical line through each blue point since only one blue point may also lie
on the boundary of a disk in the optimal solution.

  * •

For each $p_{i}\in I$, construct a disk centered at $p_{i}$ that passes
through the pair of points for which the perpendicular bisector was computed
in the previous step.

  * •

For each disk centered at $p_{i}\in I$, determine whether it contains any
point from the set ${\cal R}$. If so, remove $p_{i}$ from the set $I$.
Otherwise, compute the number of blue points contained in the disk.

  * •

If $|I|=0$, then there exists no feasible solution. Otherwise, among the disks
centered at points in $I$, select the one that contains the maximum number of
blue points.

Figure 8: The optimal solution with only one blue point for $k=1$.

######  Theorem 6.

The MaxBlue-NoRed problem for $k=1$ can be solved in $O(n^{3})$ time.

###### Proof.

In order to compute $I$, it requires $O(n^{2})$ time. If all points in the set
${\cal B}\cup{\cal R}$ have distinct $x$-coordinates, then $|I|=O(n^{2})$.
Next, for each point $p_{i}\in I$, the time required to check the interiority
of points is $O(n)$. Therefore, the total time complexity of the algorithm is
$O(n^{2})+O(n^{3})=O(n^{3})$. ∎

Improved algorithm: Here, we improve the running time of the algorithm of
Theorem 6 by almost a linear factor. Let us recall the notations, for a point
$p$, we denote its coordinates by $(x_{p},y_{p})$, and for a pair of points
$p,q$, we let $C_{p,q}$ denote the circle whose center lies on the line $y=0$
and whose boundary passes through $p,q$, and we let $(x_{p,q},0)$ denote the
center of $C_{p,q}$. Let $C_{p}$ be a circle with its boundary passing through
a point $p$, and its center lying on $\ell$ such that its radius equals
$y_{p}$ and its center at the coordinates $(x_{p},0)$.

######  Claim 3.

Given three points $p,q,r$, the point $r$ lies on or inside $C_{p,q}$ if and
only if one of the following is true:

(i) $x_{p}<x_{r}$ and $x_{p,q}\geq x_{p,r}$;

(OR)

(ii) $x_{p}>x_{r}$ and $x_{p,q}\leq x_{p,r}$.

######  Proposition 7.

There is an algorithm that accepts two sets ${\cal B},{\cal R}$ of $n$
($|{\cal B}|+|{\cal R}|$) points on the plane and finds for every pair $p,q$
of points in ${\cal B}$, the number of points of ${\cal R}$ that lie on or
inside the circle $C_{p,q}$. Further, this algorithm runs in time $O(n^{2}\log
n)$.

###### Proof.

We first describe the algorithm.

  1. 1.

Sort the point sets ${\cal B}\cup{\cal R}$ based on their $x$-coordinates from
left to right.

  2. 2.

For each $p\in{\cal B}$, compute three lists: $C_{p,{\cal
B}}=\\{x_{p,q}|q\in{\cal B}\setminus\\{p\\}\\}$, $C_{p,{\cal
R},1}=\\{x_{p,r}|r\in{\cal R}\text{ and }x_{p}<x_{r}\\}$, $C_{p,{\cal
R},2}=\\{x_{p,r}|r\in{\cal R}\text{ and }x_{p}>x_{r}\\}$.

  3. 3.

For each $p$, sort the lists $L_{p,1}=C_{p,{\cal B}}\cup C_{p,{\cal R},1}$ and
$L_{p,2}=C_{p,{\cal B}}\cup C_{p,{\cal R},2}$.

  4. 4.

For each $p$, do the following: by making a single pass over $L_{p,1}$,
compute for every $q\in{\cal B}\setminus\\{p\\}$, the value $N_{p,q,1}$, which
is defined to be the number of elements of $C_{p,{\cal R},1}$ that appear
before $x_{p,q}$ in $L_{p,1}$.

  5. 5.

For each $p$, compute for every $q\in{\cal B}\setminus\\{p\\}$, the value
$N_{p,q,2}$, which is defined to be the number of elements of $C_{p,{\cal
R},2}$ that appear after $x_{p,q}$ in $L_{p,2}$.

  6. 6.

For each $p,q$, the desired count (i.e., the number of red points covered by
the disk $C_{p,q}$) is $N_{p,q,1}+N_{p,q,2}$.

  7. 7.

To examine the scenario where only a single blue point resides on the circle,
we construct a list in the following manner:

     * •

For each $p\in{\cal B}$, we select an arbitrary point $p_{temp}$ that lies on
the circle $C_{p}$.

     * •

Let $C_{\cal B}=\\{(p,p_{temp})|\text{ $p\in{\cal B}$ and $p_{temp}$ is an
arbitrary point lying on $C_{p}$}\\}$ be a list.

     * •

Now, assign $C_{p,{\cal B}}=\\{x_{p,q}|(p,q)\in C_{\cal B}\\}$ in step 2 and
compute the lists $C_{p,{\cal R},1}$ and $C_{p,{\cal R},2}$, then repeat the
remaining steps till step 6.

  8. 8.

Lastly, we determine the circle that encloses the maximum number of blue
points and none of the red points by answering circular range counting queries
for every circle $C_{p,q}$ which has the red count $N_{p,q,1}+N_{p,q,2}=0$

Analysis: The correctness follows from Claim 3. The running time is dominated
by steps 3, 4, 5, and 8. Step 3 takes time $O(n\log n)$ for a single point $p$
and hence total time $O(n^{2}\log n)$; steps 4 and 5 take time $O(n^{2})$
each. The time complexity of Step 8 is $O(n^{2}\log{n})$ due to the repetition
of the algorithm to determine the maximum number of blue points (i.e., the
value $N_{p,q,1}+N_{p,q,2}$ is maximum for the blue points) enclosed by each
circle $C_{p,q}$ satisfying $N_{p,q,1}+N_{p,q,2}=0$ for the points in ${\cal
R}$.

∎

######  Theorem 8.

The MaxBlue-NoRed problem for $k=1$ can be solved in $O(n^{2}\log{n})$ time.

###  5.2 The AllBlue-MinRed problem for $k=1$

In [5], the problem of finding the largest and smallest disk that covers all
blue points and as few red points as possible is studied in its unrestricted
version, and in [7], they gave linear time (expected) algorithm based on
linear programming. On the other hand, in [4], the problem is studied when the
center of the disk is restricted to a line segment, which has the same time
complexity as our farthest-point Voronoi diagram based algorithm. This problem
has many bichromatic variants studied in the Ph.D. thesis [3]. Next we
describe our algorithm which is based on the farthest-point Voronoi diagram.

We first construct a farthest point Voronoi diagram ${\cal FVD}$ for the set
of blue points. Then, we find all the intersection points of Voronoi edges
with $\ell$. Since every Voronoi edge corresponds to the farthest pair of two
points, we can determine a disk centered at an intersection point of the
Voronoi edge and $\ell$, such that the disk’s boundary passes through the
respective two points. We find all such disks for each intersection point,
which are candidate locations for a facility in any feasible solution to the
AllBlue-MinRed problem for $k=1$. We pick a disk that covers the minimum
number of red points among these disks. To this end, we again employ range
searching algorithms of [6].

Figure 9: The pink disk $d_{1}$ covers all blue points with a fewer number of
red points.

######  Theorem 9.

We can solve the AllBlue-MinRed problem for $k=1$ in $O(n\log{n})$ time.

###### Proof.

The construction of the ${\cal FVD}$ concerning the blue points will take
$O(n\log{n})$ time. There will be, at most, $n$ Voronoi edges, which will
intersect with the line $\ell$. We need to find a disk among the disks
centered at all candidate locations, as identified above. This disk should
cover the minimum number of red points. To do this, we first pre-process the
red points in $O(n\log{n})$ time [6]. Each query corresponding to a disk
centered at a candidate location will take $O(\log{n})$ time [6]. Hence, the
total running time is $O(n\log{n})$. The algorithm’s correctness follows
because the Voronoi edge on which we center the disk will correspond to the
farthest pair of blue points, and the disk whose boundary passes through this
pair will cover all the blue points. ∎

##  6 Sofl on $t$-lines

Let us consider a given set ${\cal B}$ of blue points and a set ${\cal R}$ of
red points, which are positioned around $t$ parallel lines denoted as
${\ell_{1},\ell_{2},\dots,\ell_{t}}$ in the plane. These lines may have
arbitrary vertical displacements. Each point $p_{i}\in{\cal B}\cup{\cal R}$ is
assigned a weight denoted as $w_{i}$, where $w_{i}>0$ if $p_{i}\in{\cal B}$
and $w_{i}<0$ if $p_{i}\in{\cal R}$. The cardinality of the set ${\cal
B}\cup{\cal R}$ is denoted as $n$, and the interior of any geometric object
$d$ is represented as $d^{0}$ (excluding its boundary $\partial d$).

The objective is to pack $k$ non-overlapping congruent disks, denoted as
$d_{1}$, $d_{2}$, $\ldots$, $d_{k}$, with the smallest possible radius. These
disks must be centered on the parallel lines closest to the points covered by
each disk. The goal is to maximize the sum of the weights of the points
covered by the interior of the disks. This sum is represented as
$\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}$.

We may consider this as a generalization of the Sofl problem, where $t$
horizontal lines are present, and facilities can be centered on any of these
lines. Following a similar approach as in Section 3, we obtain all the
candidate radii ${\cal L}_{\textsc{can}}$ independently for each of the $t$
lines and let us denote it as ${\cal L}_{\textsc{tcan}}$. Note that the
cardinality of ${\cal L}_{\textsc{tcan}}$ is $O(tn^{2})$. Hence we have the
following lemma.

######  Lemma 3.

$|{\cal L}_{\textsc{tcan}}|=O(tn^{2})$

Next, we fix a radius $r_{\textsc{can}}\in{\cal L}_{\textsc{tcan}}$. We can
transform the problem into finding the minimum weight $k$-link path in a
directed acyclic graph (DAG) $G(V^{\prime},E^{\prime})$, as discussed in
Section 4. However, the cardinality of the set $V^{\prime}$ is $O(nkt^{2})$,
since each point $p_{i}\in{\cal B}\cup{\cal R}$ can create an influence
interval on each of the $t$ lines, resulting in $O(nt)$ endpoints of the
influence intervals and adding $O(kt)$ additional points (see Figure 10).
Figure 10 depicts the candidate locations on $\ell_{i+1}$ and $\ell_{i-1}$,
located at a distance of $2\lambda$ to the right of $p_{\ell_{i}}$. Similarly,
the mirror case can be considered for the point situated at a distance of
$2\lambda$ to the left of $p_{\ell_{i}}$ on $\ell_{i+1}$ and $\ell_{i-1}$.

Figure 10: Candidate locations corresponding to the endpoint of the infeasible
region $p_{\ell_{i}}$ and candidate radius $\lambda$.

Without loss of generality, we assume that all the points in $V^{\prime}$ have
distinct $x$-coordinates. We can construct $G^{\prime}$ in
$O(n^{2}k^{2}t^{4})$ time by employing the sweeping technique, specifically
sweeping from left to right. Therefore, the following lemma holds.

######  Lemma 4.

The DAG $G^{\prime}$ on $t$-lines can be constructed in $O(n^{2}k^{2}t^{4})$
time.

###### Proof.

Follows from the Lemma 2 as the cardinalities $|V^{\prime}|=O(nkt^{2})$ and
$|E^{\prime}|=O(n^{2}k^{2}t^{4})$. ∎

######  Theorem 10.

The Sofl problem of $t$-lines can be solved exactly in $O(n^{4}k^{2}t^{5})$
time.

###### Proof.

Follows from the Lemma 3 and Lemma 4 since there are $O(n^{2}t)$ candidate
radii and the total time is $O(n^{2}t)\times
O(n^{2}k^{2}t^{4})=O(n^{4}k^{2}t^{5})$. ∎

##  7 Discrete Sofl with all facility sites in convex position

Suppose we are given a set $\cal B$ of blue points, a set $\cal R$ of red
points, and a set ${\cal F}$ of $s$ candidate locations in convex position;
all these three sets are 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}$, …,
$d_{k}$ of minimum radius, centered at points in ${\cal F}$ 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}^{k}d_{j}$ is maximized.

The above problem is a discrete variation of the Sofl problem (Dsofl) because
a finite number of candidate facility sites (in convex position) are pre-
given. Even though it is the discrete version of the Sofl problem, similar to
the continuous line case, we know that there exists only a constant number of
critical configuration types for the points in $\mathcal{R}\cup\mathcal{B}$
and candidate facilities in $\mathcal{F}$. It follows from the latter that we
also have a finite number of candidate radii here. Let
$\mathcal{L}_{\textsc{Dcan}}$ denote the set of all candidate radii.

######  Lemma 5.

$|\mathcal{L}_{\textsc{Dcan}}|=O(ns)$.

###### Proof.

Since there will be only a constant number of critical configuration types
concerning points $\mathcal{B}\cup\mathcal{R}$ and candidate facilities
$\mathcal{F}$, we can consider the following situation where the candidate
radius is determined based on a point in $\mathcal{B}\cup\mathcal{R}$ and a
candidate facility location (on whose boundary that point lies) in
$\mathcal{F}$. The cardinality of the set of radii from this situation is
$O(ns)$ (see Figure 11).

Figure 11: The blue point $p_{i}$ lying on the boundary of $d_{3}$ will
determine the radius. Figure 12: Illustration of the candidate facilities will
not determine the radius of disks in the optimal packing.

The radius of the disks in the optimal packing cannot be determined solely by
the distance between the candidate sites (see Fig 12). In Figure 12, we can
observe that the closest pair of disks $d_{i-1}$ and $d_{i}$ will never touch
in any optimal packing (i.e., the distance between them will not determine the
radii of the disks in the optimal packing). Suppose they touch in any optimal
packing, then we can reduce the radii of the disks until one of the blue
points lie on the boundary of any of the disk (see Figure 12, $p_{i}$ lying on
the boundary of the disk $d_{i-1}$). ∎

###  7.1 Dynamic programming algorithm

In this section, first, we show a relationship between the Voronoi diagram of
points in an optimal solution and the cost of an optimal solution to the Dsofl
problem. We then present a dynamic programming-based solution for the discrete
Sofl problem utilizing this property of the Voronoi diagram ($\mathcal{VD}$)
of the $k$ sites in an optimal solution. This process is repeated for each
$\lambda\in\mathcal{L}_{\textsc{Dcan}}$. The Voronoi diagram of points in
convex position forms a tree-like structure except for its infinite edges. If
we overlay the diagram with a sufficiently big bounding rectangle, we have the
following observation.

######  Observation 5.

The Voronoi diagram of points in convex position is a tree.

Since the points in $\mathcal{F}$ are in convex position, Observation 5
implies that the $\mathcal{VD}$ of any subset of points in $\mathcal{F}$ is
also a tree. Hence, $\mathcal{VD}$ of the optimal $k$ facility sites is a
tree. This $\mathcal{VD}$ tree structure allows us to employ dynamic
programming. To find this tree or a subtree of it from its rightmost node, we
define a subproblem that explores all possible edges from the rightmost node
and then further this exploration recursively. This leads to recursively
constructing an optimal solution once we guess the rightmost node of the tree.
Furthermore, we show no circular dependencies between subproblems.

Without loss of generality, let us consider that the points in ${\cal
F}=\\{p_{1},p_{2},\dots,p_{s}\\}$ are ordered clockwise. It is known that the
Delaunay triangulation is the dual of the Voronoi diagram. Denote ${\cal DT}$
as the Delaunay triangulation formed by the points corresponding to the
Voronoi centers in the Voronoi diagram, ${\cal VD}$. Observe that the smallest
edge length of ${\cal DT}$ of points in an optimal solution to Dsofl is at
least twice the radius of disks in the optimal solution.

For a given $\lambda\in\mathcal{L}_{\textsc{Dcan}}$, we precalculate the
weight of points covered by a disk with radius $\lambda$ centered at a
facility site $f_{i}\in{\cal F}$ and denote this weight as $w(f_{i})$. Then,
our dynamic program-based algorithm is as follows. First, we guess the
Delaunay triangle corresponding to the rightmost Voronoi node, the three
rightmost facility centers, say, $p_{i},p_{\ell},p_{j},$ (where $p_{l}$ is the
rightmost and $p_{i}$ is below $p_{j}$) in the optimal solution. We make all
possible $s\choose 3$ guesses to find these three optimal centers. Then,
define a subproblem $\Gamma(p_{i},p_{\ell},p_{j},{\cal F^{\prime}};{\cal K})$,
which corresponds to the maximum (optimal) weight of the points covered by
${\cal K}$ facilities located at some points in $\mathcal{F}$ with a radius of
$\lambda$, and the points $p_{i}$, $p_{\ell}$ and $p_{j}$ are the rightmost
ordered points in the optimal solution. Initially, we set ${\cal K}=k-3$ and
${\cal F^{\prime}}={\cal F}\setminus\\{p_{i},\dots,p_{\ell},\dots,p_{j}\\}$,
where the indices $i,j,\ell,\ell^{\prime}$ are to be read modulo $s$. Now,
consider reconstructing ${\cal VD}$ with three $p_{i}$, $p_{j},p_{\ell}$ fixed
on the right. We do this by determining the corresponding ${\cal DT}$ triangle
with its corner points $p_{i}$, $p_{j}$ and $p_{\ell^{\prime}}$. We extend the
${\cal VD}$ by choosing the next point $p_{\ell^{\prime}}$ that lies left of
$\overrightarrow{p_{j}p_{i}}$ such that it is at least $2\lambda$ from
$p_{i}$, $p_{j}$ and $p_{\ell}$. Observe that $p_{\ell^{\prime}}$ is outside
the circumcircle of $p_{i}$, $p_{j}$ and $p_{\ell}$. Then we have the
following recurrence,

$\Gamma(p_{i},p_{\ell},p_{j},{\cal F^{\prime}};{\cal K})=$

$\begin{split}\max_{\begin{subarray}{c}{\cal K}^{\prime}\leq{\cal K}-1,\\\
p_{\ell^{\prime}}\in{\cal F^{\prime}}and\\\
p_{\ell^{\prime}}:\zeta(p_{\ell^{\prime}},\\{p_{i},p_{j},p_{\ell}\\})\geq
2\lambda\end{subarray}}\begin{cases}w(p_{\ell^{\prime}})+\Gamma(p_{\ell^{\prime}},p_{i},p_{j},{\cal
F^{\prime\prime}};{\cal
K}^{\prime})+\Gamma(p_{\ell^{\prime}},p_{j},p_{i},{\cal
F^{\prime\prime\prime}};{\cal K}-1-{\cal K}^{\prime})&\text{ if }|{\cal
F^{\prime}}|\geq 1\\\ 0&\text{ otherwise}\end{cases}\end{split}$

where
$\zeta(p_{\ell^{\prime}},\\{p_{i},p_{j},p_{\ell}\\})=\min\\{dist(p_{\ell^{\prime}},p_{i}),dist(p_{\ell^{\prime}},p_{j}),dist(p_{\ell^{\prime}},p_{\ell})\\}$,
$w(p_{\ell^{\prime}})$ denotes the total weight of the points that are covered
by a disk of radius $\lambda$ centered at $p_{\ell^{\prime}}$, ${\cal
F^{\prime\prime}}={\cal
F^{\prime}}\setminus\\{p_{j},\dots,p_{\ell^{\prime}}\\}$ and ${\cal
F^{\prime\prime\prime}}={\cal
F^{\prime}}\setminus\\{p_{\ell^{\prime}},\dots,p_{i}\\}$. Base cases are
$\Gamma(p_{i},p_{\ell},p_{j},{\cal
F^{\prime}};0)=w(p_{i})+w(p_{\ell})+w(p_{j})$,
$\Gamma(p_{i},p_{\ell},p_{j},\emptyset;{\cal K})=0$.

#### Proof of Correctness:

The correctness of the dynamic programming algorithm can be established based
on the following observations:

  * •

The minimum edge length of ${\cal DT}$ formed by the $k$ sites in the optimal
solution is at least $2\lambda$. This ensures that the disks in the optimal
solution do not overlap, as the distance between any two points in the
solution is greater than or equal to $2\lambda$.

  * •

There always exists a solution for a given set of points ${\cal B}\cup{\cal
R}$ and ${\cal F}$. If it is impossible to place $k$ disks with a radius of
$\lambda$, the algorithm returns a zero weight, indicating that a solution
does not exist for given $\lambda$.

  * •

By assuming that $p_{i}$, $p_{\ell}$, and $p_{j}$ are the rightmost points in
the optimal solution, we have $O(s^{3})$ choices for these points. This
assumption ensures that a ${\cal DT}$ with $k$ vertices corresponding to the
optimal solution always exists if a solution exists for a given $\lambda$.

Based on these observations, we can conclude that the dynamic programming
algorithm is correct in determining the optimal solution for the given set of
points ${\cal B}\cup{\cal R}$ and ${\cal F}$, considering the assumptions made
and the properties of the ${\cal DT}$ formed by the candidate sites.

######  Theorem 11.

Discrete Sofl with candidate facility sites in convex position can be solved
in polynomial time.

###### Proof.

The running time of the algorithm is calculated as follows:

  * •

From Lemma 5 we have $|\mathcal{L}_{\textsc{Dcan}}|=O(ns)$.

  * •

For each $\lambda\in{\cal L}_{\textsc{tcan}}$ we call the dynamic programming
algorithm.

  * •

Dynamic programming algorithm for a given $\lambda$:

    * –

For each $f_{i}\in{\cal F}$, calculating weight of points covered by a disk of
radius $\lambda$ centered at $f_{i}$ will take $(ns)$ time.

    * –

There are $O(s^{3}k)$ subproblems and each subproblem will take $O(sk)$ time.

  * •

The total time complexity of the algorithm is $O(n^{2}s^{2}+ns^{5}k^{2})$.
Additionally, we designate the vertices of ${\cal DT}$ as the optimal solution
that yields the maximum weight out of all the invocations of the dynamic
programming algorithm with three rightmost points $p_{i}$, $p_{j}$,
$p_{\ell}$.

∎

##  8 Conclusion

This paper studied the problem of locating $k$ semi-obnoxious facilities
constrained to a line (CSofl) when the given demand points have positive and
negative weights. Specifically, we solved the problem of locating $k$ semi-
obnoxious facilities on a line to locate facilities with the maximum weight of
the covered demand points in $O(n^{4}k^{2})$ time. Subsequently, we improved
the running time to $O(n^{3}k\cdot\max{(n,k)})$. Furthermore, we addressed two
special cases of the problem where points do not have arbitrary weights. We
showed that these two special cases can be solved in
$O(n^{3}k\cdot\max{(\log{n},k)})$ time. For the first case, when $k=1$, we
also provide an algorithm that solves the problem in $O(n^{3})$ time, and
subsequently, we improve this result to $O(n^{2}\log{n})$. For the latter
case, we give $O(n\log{n})$ time algorithm that uses the farthest point
Voronoi diagram. We also studied the Sofl for $t$-lines and showed that it can
be solved in polynomial time but with a high order degree in $t$. Further, we
investigated the complexity of discrete semi-obnoxious facility location
(DSofl) for the given candidate locations in convex position, and we showed
that this problem can also be solved in polynomial time.

Following are some of the open problems that are worth considering as future
work:

  * •

The continuous unrestricted variant of the semi-obnoxious facility location
problem: given two sets (red and blue) of demand points with positive and
negative weights (respectively) in the plane and an integer $k$. The objective
is to maximize the sum of the weights of the points covered by the union of
$k$ congruent non-overlapping disks of minimum radius centered anywhere in the
plane (i.e., disks (facilities) may be centered anywhere in the plane).

  * •

The discrete unrestricted variant of the semi-obnoxious facility location
problem: given two sets (red and blue) of points with positive and negative
weights (respectively), a set of candidate facility locations in the plane,
and an integer $k$. The objective is to maximize the sum of the weights of the
points covered by the union of $k$ congruent non-overlapping disks of minimum
radius centered at some of the candidate facility locations.

  * •

To investigate the scenario when the disks are centered on the boundary of a
convex polygon instead of a horizontal line or at vertices of convex polygon.

  * •

To investigate the scenario when the disks are restricted to be centered at
the grid points of a $t\times t$ grid in the plane.

  * •

Finding a better than $O(n^{2}\log n)$ time algorithm for the MaxBlue-NoRed
problem for $k=1$.

## References

  * Abidha and Ashok [2022] VP Abidha and Pradeesha Ashok.  Geometric separability using orthogonal objects.  _Information Processing Letters_ , 176:106245, 2022.
  * Aggarwal et al. [1993] Alok Aggarwal, Baruch Schieber, and Takashi Tokuyama.  Finding a minimum weight k-link path in graphs with monge property and applications.  In _Proceedings of the ninth annual symposium on Computational geometry_ , pages 189–197, 1993.
  * Armaselu [2017] Bogdan Andrei Armaselu.  _On the geometric separability of bichromatic point sets_.  PhD thesis, 2017.
  * Bereg et al. [2015] Sergey Bereg, Ovidiu Daescu, Marko Zivanic, and Timothy Rozario.  Smallest maximum-weight circle for weighted points in the plane.  In _Computational Science and Its Applications–ICCSA 2015: 15th International Conference, Banff, AB, Canada, June 22-25, 2015, Proceedings, Part II_ , pages 244–253. Springer, 2015.
  * Bitner et al. [2010] Steven Bitner, Yam Cheung, and Ovidiu Daescu.  Minimum separating circle for bichromatic points in the plane.  In _2010 International Symposium on Voronoi Diagrams in Science and Engineering_ , pages 50–55. IEEE, 2010.
  * Chan and Tsakalidis [2016] Timothy M Chan and Konstantinos Tsakalidis.  Optimal deterministic algorithms for 2-d and 3-d shallow cuttings.  _Discrete & Computational Geometry_, 56:866–881, 2016\.
  * Cheung et al. [2010] Yam Cheung, Ovidiu Daescu, and TX Richardson.  Minimum separating circle for bichromatic points by linear programming.  _Proc. FWCG_ , 2010.
  * Coutinho-Rodrigues et al. [2012] João Coutinho-Rodrigues, Lino Tralhão, and Luís Alçada-Almeida.  A bi-objective modeling approach applied to an urban semi-desirable facility location problem.  _European journal of operational research_ , 223(1):203–213, 2012.
  * Edelsbrunner and Preparata [1988] H. Edelsbrunner and F.P. Preparata.  Minimum polygonal separation.  _Information and Computation_ , 77(3):218–232, 1988.  ISSN 0890-5401.  doi:https://doi.org/10.1016/0890-5401(88)90049-1.
  * Fekete [1992] Sandor Fekete.  On the complexity of min-link red-blue separation.  _Manuscript, department of applied mathematics, SUNY Stony Brook, NY_ , 1992.
  * Gholami and Fathali [2021] Mehraneh Gholami and Jafar Fathali.  The semi-obnoxious minisum circle location problem with euclidean norm.  _International Journal of Nonlinear Analysis and Applications_ , 12(1):669--678, 2021.
  * Golpayegani et al. [2014] Mehdi Golpayegani, Jafar Fathali, and Eiman Khosravian.  Median line location problem with positive and negative weights and euclidean norm.  _Neural Computing and Applications_ , 24:613--619, 2014\.
  * Golpayegani et al. [2017] Mehdi Golpayegani, Jafar Fathali, and Haleh Moradi.  A particle swarm optimization method for semi-obnoxious line location problem with rectilinear norm.  _Computers & Industrial Engineering_, 109:71--78, 2017\.
  * Maranas and Floudas [1994] Costas D Maranas and Christodoulos A Floudas.  A global optimization method for weber’s problem with attraction and repulsion.  _Large scale optimization: State of the art_ , pages 259--285, 1994\.
  * Melachrinoudis and Xanthopulos [2003] Emanuel Melachrinoudis and Zaharias Xanthopulos.  Semi-obnoxious single facility location in euclidean space.  _Computers & Operations Research_, 30(14):2191--2209, 2003.
  * Mitchell [1993] Joseph SB Mitchell.  Approximation algorithms for geometric separation problems.  Technical report, State University of New York at Stony Brook, 1993.  URL http://www.ams.sunysb.edu/~jsbm/papers/sep-2-10-94.pdf.
  * O’rourke et al. [1986] Joseph O’rourke, S Rao Kosaraju, and Nimrod Megiddo.  Computing circular separability.  _Discrete & Computational Geometry_, 1:105--113, 1986\.
  * Singireddy and Basappa [2021] Vishwanath R Singireddy and Manjanna Basappa.  Constrained obnoxious facility location on a line segment.  In _33rd Canadian Conference on Computational Geometry_ , pages 362--367, 2021.
  * Singireddy and Basappa [2022] Vishwanath R Singireddy and Manjanna Basappa.  Dispersing facilities on planar segment and circle amidst repulsion.  In _Algorithmics of Wireless Networks: 18th International Symposium on Algorithmics of Wireless Networks, ALGOSENSORS 2022, Potsdam, Germany, September 8--9, 2022, Proceedings_ , pages 138--151. Springer, 2022.
  * Teran-Somohano and Smith [2019] Alejandro Teran-Somohano and Alice E Smith.  Locating multiple capacitated semi-obnoxious facilities using evolutionary strategies.  _Computers & Industrial Engineering_, 133:303--316, 2019\.
  * Wagner [2015] Andrea Wagner.  A new duality based approach for the problem of locating a semi-obnoxious facility.  2015\.
  * Zhang [2022] Bowei Zhang.  Efficient algorithms for obnoxious facility location on a line segment or circle.  _arXiv preprint arXiv:2210.07146_ , 2022.