(𝒏, 𝟏, 𝟏, 𝜶)-Center Problem

Given a set 𝑆 of 𝑛 points in the plane and a constant 𝛼,(𝑛, 1, 1, 𝛼)-center problem is to find two closed disks which each covers the whole 𝑆, the diameter of the bigger one is minimized, and the distance of the two centers is at least 𝛼. Constrained (𝑛, 1, 1, 𝛼)-center problem is the (𝑛, 1, 1, 𝛼)-center problem in which the centers are forced to lie on a given line 𝐿. In this paper, we first introduce (𝑛, 1, 1, 𝛼)-center problem and its constrained version. Then, we present an 𝑂(𝑛 log 𝑛) algorithm for solving the (𝑛, 1, 1, 𝛼)-center problem