On the Planar Two-Center Problem and Circular Hulls^††thanks: A preliminary version of this paper will appear in the Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020).

In this paper, we consider the planar 2-center problem. Given a set $S$ of $n$ points in the Euclidean plane, we wish to find two congruent disks of smallest radius whose union covers all points of $S$.

The classical 1-center problem for a set of points is to find the smallest disk covering all points, and the problem can be solved in linear time in any fixed dimensional space [9, 13, 23]. As a natural generalization, the 2-center problem has attracted much attention. Hershberger and Suri [18] first solved the decision version of the problem in $O(n^{2}\log n)$ time, which was later improved to $O(n^{2})$ time [17]. Using this result and parametric search [22], Agarwal and Sharir [2] gave an $O(n^{2}\log^{3}n)$ time algorithm for the $2$-center problem. Katz and Sharir [20] achieved the same running time by using expanders instead of parametric search. Eppstein [15] presented a randomized algorithm of $O(n^{2}\log^{2}n\log\log n)$ expected time. Later, Jaromczyk and Kowaluk [19] proposed an $O(n^{2})$ time algorithm. A breakthrough was achieved by Sharir [27], who proposed the first subquadratic algorithm for the problem, and the running time is $O(n\log^{9}n)$. Afterwards, following Sharir’s algorithmic scheme, Eppstein [16] derived a randomized algorithm of $O(n\log^{2}n)$ expected time, and then Chan [6] developed an $O(n\log^{2}n\log^{2}\log n)$ time deterministic algorithm and a randomized algorithm of $O(n\log^{2}n)$ time with high probability. Recently, Tan and Jiang [28] proposed a simple algorithm of $O(n\log^{2}n)$ time based on binary search, but unfortunately, the algorithm is not correct (see the appendix for details). The problem has an $\Omega(n\log n)$ time lower bound in the algebraic decision tree model [16], by a reduction from the max-gap problem.

In this paper, we present a new deterministic algorithm of $O(n\log^{2}n)$ time, which improves the $O(n\log^{2}n\log^{2}\log n)$ time deterministic algorithm by Chan [6] and matches the randomized bound of $O(n\log^{2}n)$ [6, 16]. This is the first progress on the problem since Chan’s work [6] was published twenty years ago. Further, if $S$ is in convex position (i.e., every point of $S$ is a vertex of the convex hull of $S$), then our technique can solve the 2-center problem on $S$ in $O(n\log n\log\log n)$ time. Previously, Kim and Shin [21] announced an $O(n\log^{2}n)$ time algorithm for this convex position case, but Tan and Jiang [28] found errors in their time analysis.

Some variations of the 2-center problem have also been considered in the literature. Agarwal et al. [3] studied the discrete 2-center problem where the centers of the two disks must be in $S$, and they solved the problem in $O(n^{4/3}\log^{5}n)$ time. Agarwal and Phillips [1] considered an outlier version of the problem where $k$ points of $S$ are allowed to be outside the two disks, and they presented a randomized algorithm of $O(nk^{7}\log^{3}n)$ expected time. Arkin et al. [4] studied a bichromatic 2-center problem for a set of $n$ pairs of points in the plane, and the goal is to assign a red color to a point and a blue color to the other point for every pair, such that $\max\{r_{1},r_{2}\}$ is minimized, where $r_{1}$ (resp., $r_{2}$) is the radius of the smallest disk covering all red (resp., blue) points. Arkin et al. [4] gave an $O(n^{3}\log^{2}n)$ time algorithm, which was recently improved to $O(n^{2}\log^{2}n)$ time by Wang and Xue [29]. The more general $k$-center problem is NP-hard if $k$ is part of the input [24].

We begin with some notation, some of which is borrowed from [6]. It suffices to solve the nearby case. Thus, we assume that $\delta^{*}<r^{*}$ in the rest of the paper. In the nearby case, it is possible to find in $O(n)$ time a constant number of points such that at least one of them, denoted by $o$, is in $D_{1}^{*}\cap D_{2}^{*}$ [16]. We assume that $o$ is the origin of the plane. We make a general position assumption: no two points of $S$ are collinear with $o$ and no two points of $S$ have the same $x$-coordinate. This assumption does not affect the running time of the algorithm, but simplifies the presentation.

For any set $P$ of points in the plane, let $\tau(P)$ denote the radius of the smallest enclosing disk of $P$. For a connected region $B$ in the plane, let $\partial B$ denote the boundary of $B$.

The boundaries of the two disks $D^{*}_{1}$ and $D^{*}_{2}$ have exactly two intersections, and let $\rho_{1}$ and $\rho_{2}$ be the two rays through these intersections emanating from $o$ (e.g., see Fig. 2). As argued in [6], one of the two coordinate axes must separate $\rho_{1}$ and $\rho_{2}$ since the angle between the two rays lies in $[\pi/2,3\pi/2]$, and without loss of generality, we assume it is the $x$-axis.

Let $S^{+}$ denote the subset of points of $S$ above the $x$-axis, and $S^{-}=S\setminus S^{+}$. For notational simplicity, let $|S^{+}|=|S^{-}|=n$. Let $p_{1},p_{2},\ldots,p_{n}$ be the sorted list of $S^{+}$ counterclockwise around $o$, and $q_{1},q_{2},\ldots,q_{n}$ the sorted list of $S^{-}$ also counterclockwise around $o$ (e.g., see Fig. 2). For each $i=0,1,\ldots,n$ and $j=0,1,\ldots,n$, define $L_{ij}=\{p_{i+1}\ldots,p_{n},q_{1},\ldots,q_{j}\}$ and $R_{ij}=\{q_{j+1},\ldots,q_{n},p_{1},\ldots,p_{i}\}$. Note that if $i=n$, then $L_{ij}=\{q_{1},\ldots,q_{j}\}$, and if $j=n$, then $R_{ij}=\{p_{1},\ldots,p_{i}\}$. In words, if we consider a ray emanating from $o$ and between $p_{i}$ and $p_{i+1}$, and another ray emanating from $o$ and between $q_{j}$ and $q_{j+1}$, then $L_{ij}$ (resp., $R_{ij}$) consist of all points to the left (resp., right) of the two rays (e.g., see Fig. 2).

Note that the partition of $S$ by the two rays $\rho_{1}\cup\rho_{2}$ is $\{L_{ij},R_{ij}\}$ for some $i$ and $j$, and thus $r^{*}=\max\{\tau(L_{ij}),\tau(R_{ij})\}$. Define $A[i,j]=\tau(L_{ij})$ and $B[i,j]=\tau(R_{ij})$, for all $0\leq i,j\leq n$. Then, $r^{*}=\min_{0\leq i,j\leq n}\max\{A[i,j],B[i,j]\}$. If we consider $A$ and $B$ as $(n+1)\times(n+1)$ matrices, then each row of $A$ (resp., $B$) is monotonically increasing (resp., decreasing) and each column of $A$ (resp., $B$) is monotonically decreasing (resp., increasing). For each $i\in[0,n]$, define $r^{*}_{i}=\min_{0\leq j\leq n}\max\{A[i,j],B[i,j]\}$. Thus, $r^{*}=\min_{0\leq i\leq n}r_{i}^{*}$.

This section is concerned with the decision problem: Given a value $r$, decide whether $r^{*}\leq r$. Previously, Chan [6] solved the problem in $O(n\log n)$ time (Chan actually considered a slightly different problem: decide whether $r^{*}<r$, but the idea is similar). We present an $O(n)$ time algorithm, after $O(n\log n)$ time preprocessing to sort all points of $S^{+}$ and $S^{-}$ to obtain the sorted lists $p_{1},\ldots,p_{n}$ and $q_{1},\ldots,q_{n}$.

Given $r$, we use the following algorithmic framework in Algorithm 1 from [6] (see Theorem 3.3), which can decide whether $r^{*}\leq r$, and if yes, report all indices $i$ with $r_{i}^{*}\leq r$.

The algorithm is simple, but the technical crux is in how to decide whether $A[i,j+1]\leq r$ and whether $B[i,j]\leq r$. Chan [6] built a data structure in $O(n\log n)$ time so that each of these two steps can be done in $O(\log n)$ time, which leads to an overall $O(n\log n)$ time for his decision algorithm. Our innovation is a new data structure that can perform each of the two steps in $O(1)$ amortized time, resulting in an $O(n)$ time algorithm. Our idea is motivated by the following observation.

We call such a path in $A$ as specified in the observation a monotone path, which contains at most $2(n+1)$ elements of $A$. We show that we can determine in $O(n)$ time whether $A[i,j]\leq r$ for all elements $A[i,j]$ in a monotone path of $A$. The same algorithm works for $B$ as well.

Let $\pi$ be a monotone path of $A$, starting from $A[0,0]$. Consider any element $A[i,j]$ on $\pi$. Recall that $A[i,j]=\tau(L_{ij})$. The next value of $\pi$ after $A[i,j]$ is either $A[i,j+1]$ or $A[i+1,j]$, i.e., either $\tau(L_{i,j+1})$ or $\tau(L_{i+1,j})$. Note that $L_{i,j+1}$ can be obtained from $L_{ij}$ by inserting $q_{j+1}$ and $L_{i+1,j}$ can be obtained from $L_{ij}$ by deleting $p_{i+1}$. Because the points $p_{1},p_{2},\ldots,p_{n},q_{1},q_{2}\ldots,q_{n}$ are ordered around $o$ counterclockwise, our problem becomes the following. Maintain a sublist $Q$ of the above sorted list of $S$, with $Q=S^{+}$ initially, to determine whether $\tau(Q)\leq r$ (or equivalently whether $\alpha_{r}(Q)$ exists) under deletions and insertions, such that a deletion operation deletes the first point of $Q$ and an insertion operation inserts the point of $S$ following the last point of $Q$. Further, deletions only happen to points of $S^{+}$ (i.e., once $p_{n}$ is deleted from $Q$, no deletions will happen). We refer to the problem as the dynamic circular hull problem. We will show in Section 6 that the problem can be solved in $O(n)$ time, i.e., each update takes $O(1)$ amortized time. This leads to the following result.

With Theorem 3.1, we solve the optimization problem by parametric search [10, 22]. As Chan’s algorithm [6], because our decision algorithm is inherently sequential, we need to design a parallel decision algorithm. Chan [6] gave a parallel decision algorithm that runs in $O(\log n\log^{2}\log n)$ parallel steps using $O(n\log n)$ processors. Consequently, by using his $O(n\log n)$ time decision algorithm and applying Cole’s parametric search [10], Chan [6] solved the optimization problem in $O(n\log^{2}n\log^{2}\log n)$ time. By following Chan’s algorithmic scheme, we develop a new parallel decision algorithm that runs in $O(\log n\log\log n)$ parallel steps using $O(n)$ processors. Then, with the serial decision algorithm in Theorem 3.1 and applying Cole’s parametric search [10] on our new parallel decision algorithm, we solve the optimization problem in $O(n\log n\log\log n)$ time.

Our algorithm relies on the following lemma, whose proof is quite independent of the remainder of this section and will be given in Section 7. Note that Hershberger and Suri [18] gave a linear-time algorithm to achieve the same result as Lemma 1, which suffices for their purpose.

For any $0\leq i\leq j\leq n$, let $S^{+}[i,j]=\{p_{i},p_{i+1},\ldots,p_{j}\}$ and $S^{-}[i,j]=\{q_{i},q_{i+1},\ldots,q_{j}\}$. By using Lemma 1, we have the following lemma.