Linear-Time $(1+\epsilon )$-Approximation Algorithms for Two-Line-Center Problems

Given a set $S$ of $n$ points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in $S$ to its closest line. This is a special case of the $k$-line-center problem, which asks, for a given set $S$ of $n$ points in the plane, to find $k$ lines minimizing the maximum distance from each point in $S$ to its closest line. A more general framework is projective clustering: Given $P\subset {ℝ}^d$, the goal is to find $k$ flats of dimension $j$ that best fit $P$ under a given distance measure. It has wide applications in data mining [4, 5], unsupervised learning [23], database management [10], and computer vision [24].

The $k$-line-center problem is known to be NP-hard [21] when $k$ is part of the input (even in the plane), and various approaches including approximation algorithms and randomized methods [1, 3, 7, 9, 11, 13, 16, 17, 18] have been studied.

When $k=1$, the problem becomes computing the width of a point set. This can be done exactly in $O(n\log n)$ time [22], and an $\mathrm{\Omega }(n\log n)$ lower bound is known [20]. A $(1+\epsilon )$-approximation algorithm running in $O(n+1/\epsilon )$ time was given in [11].

When $k=2$, i.e., the two-line-center problem, an exact algorithm with running time $O(n^2{\log }^{2}n)$ is known [19]. The authors in [2] presented a $(1+\epsilon )$-approximation algorithm that runs in $O(n\log n+(n/{\epsilon }^2)\log (1/\epsilon )+{\epsilon }^{-7/2}\log (1/\epsilon ))$ time. Later, as the $(1+\epsilon )$-approximation algorithm for the width problem was improved from $O(n+{\epsilon }^{-3/2})$ to $O(n+1/\epsilon )$ [11], their algorithm is consequently improved to $O(n\log n+(n/{\epsilon }^2)\log (1/\epsilon )+(1/{\epsilon }^3)\log (1/\epsilon ))$, even though it is not explicitly mentioned.

Observe that the two-line-center problem is equivalent to finding a pair of slabs whose union covers the input point set while minimizing their maximum width.

We study the two-line-center problem and three natural variants. Let $\mu =\min \{n,\mathrm{\hspace{0.17em}1}/{\epsilon }^2\}$, and let $w^{\ast }$ denote the maximum width of an optimal pair of slabs in each problem. Each variant is illustrated in Figure 1. Table 1 summarizes the previous and new results.

1. 1.

   General: Given a set $S$ of $n$ points in the plane, we study the problem of finding a pair of slabs whose union covers $S$ while minimizing the maximum of their widths. We present an $O(n+(\mu /\epsilon )\log \mu )$-time algorithm that finds a pair of slabs whose union covers $S$ and whose maximum width is at most $(1+\epsilon )w^{\ast }$. The running time can be expressed as both $O((n/\epsilon )\log (1/\epsilon ))$ and $O(n+(1/{\epsilon }^3)\log (1/\epsilon ))$.

2. 2.

   One Fixed Orientation: Given a set $S$ of $n$ points in the plane and an orientation $\theta$, we study the problem of finding a pair of slabs such that one of them has orientation $\theta$ and their union covers $S$ while minimizing the maximum of their widths. We present an exact algorithm that runs in $O(n\log n)$ time, improving the previously best $O(n{\log }^{3}n)$-time algorithm [6], and show that this is optimal.

     We also present an $O(n+\mu \log \mu )$-time algorithm that finds a pair of slabs such that one of them has orientation $\theta$, their union covers $S$, and their maximum width is at most $(1+\epsilon )w^{\ast }$. The running time can be expressed as $O(n\log (1/\epsilon ))$ and $O(n+1/{\epsilon }^2\log (1/\epsilon ))$.

3. 3.

   Two Fixed Orientations: Given a set $S$ of $n$ points in the plane and two orientations, ${\theta }_1$ and ${\theta }_2$, we study the problem of finding two slabs, one has orientation ${\theta }_1$ and the other has orientation ${\theta }_2$, whose union covers $S$ while minimizing the maximum of their widths. We present an $O(n+1/\epsilon )$-time algorithm that finds a pair of slabs such that one has orientation ${\theta }_1$ and the other has orientation ${\theta }_2$, their union covers $S$, and their maximum width is at most $(1+\epsilon )w^{\ast }$.

4. 4.

   Parallel: Given a set $S$ of $n$ points in the plane, we study the problem of finding a pair of parallel slabs whose union covers $S$ while minimizing the maximum of their widths. We present an $O(n+\mu /\epsilon )$-time algorithm that finds a pair of parallel slabs such that their union covers $S$ and their maximum width is at most $(1+\epsilon )w^{\ast }$.

For a set $P$ of points in the plane, we denote its diameter by $\mathrm{diam}(P)$, its width by $0pt(P)$, and its convex hull by $\mathrm{conv}(P)$. If $P=\mathrm{\varnothing }$, then $0pt(P)=0$. For a slab $\sigma$, we denote its width by $w(\sigma )$, which is the distance between the two bounding lines of $\sigma$ (see Figure 2(a)).

For a line $\mathrm{\ell }$, we say that $\mathrm{\ell }$ has orientation $\theta \in [0,\pi )$ if $\theta$ is the counterclockwise angle from the $x$-axis to $\mathrm{\ell }$. A slab $\sigma$ is said to have orientation $\theta \in [0,\pi )$ if its two bounding lines have orientation $\theta$ (see Figure 2(a)). For a finite set $P$ of points in the plane, let ${\sigma }_{\theta }(P)$ denote the minimum-width slab of orientation $\theta$ that encloses $P$, and define $0p{t}_{\theta }(P)=w({\sigma }_{\theta }(P))$ (see Figure 2(b)).

For a set $P$ of points in the plane and an orientation $\theta \in [0,\pi )$, we say that a pair $(p,q)$ with $p,q\in P$ is an antipodal pair of $P$ with respect to $\theta$ if $p$ lies on one bounding line of ${\sigma }_{\theta }(P)$ and $q$ lies on the other (see Figure 2(b)).

For two finite sets $A$ and $B$ in the plane, let $d(A,B)$ denote the minimum distance between a point of $A$ and a point of $B$. For two points $p$ and $q$ in the plane, let ${\mathrm{\ell }}_{pq}$ be the line passing through $p$ and $q$.

For each of the four problems, we assume that $w^{\ast }>0$, where $w^{\ast }$ denotes the maximum width of an optimal pair of slabs for that problem. The case where $w^{\ast }=0$ can be detected and handled in linear time. See the appendix in the full version.

Throughout the paper, let $\epsilon >0$ be a sufficiently small real number and let $S$ denote an input set of $n$ points in the plane. Due to space constraints, the proofs of the theorems and lemmas marked with a star(^∗) are provided in the full version.

In this section, we describe three key ingredients used throughout the paper: (1) an anchor pair, (2) a linear-time $10$-approximation algorithm, and (3) an $\epsilon$-certificate.

Throughout this section, we denote by ${\mathrm{\Sigma }}^{\ast }=({\sigma }_1^{\ast },{\sigma }_2^{\ast })$ an optimal pair of slabs for the general two-line-center problem, and let $w^{\ast }=\max \{w({\sigma }_1^{\ast }),w({\sigma }_2^{\ast })\}$.

By rotating the coordinate system, we assume without loss of generality that the given orientation $\theta$ is $0$. Throughout this section, we denote by $({\sigma }_1^{\ast },{\sigma }_2^{\ast })$ an optimal pair of slabs for the one-fixed-orientation problem, where ${\sigma }_1^{\ast }$ is horizontal. Let $w^{\ast }=\max \{w({\sigma }_1^{\ast }),w({\sigma }_2^{\ast })\}$.

Throughout this section, we denote by ${\mathrm{\Sigma }}^{\ast }=({\sigma }_1^{\ast },{\sigma }_2^{\ast })$ an optimal pair of slabs for the general two-line-center problem. Let $w^{\ast }=\max \{w({\sigma }_1^{\ast }),w({\sigma }_2^{\ast })\}$.

We begin by proving Lemma 5, which will be used to compute a candidate set of orientations for one of the slabs in a $(1+\epsilon )$-approximate solution.

By Lemma 3.1, we can compute a set $F$ of at most $11$ pairs such that one of them is an anchor pair of ${\mathrm{\Sigma }}^{\ast }$ in $O(n)$ time. For the moment, assume that we have an anchor pair $(p,q)$ of ${\mathrm{\Sigma }}^{\ast }$. (We will repeat the following process for every pair in $F$.) Without loss of generality, assume that $p,q\in {\sigma }_1^{\ast }$ and $d(p,q)\ge diam(({\sigma }_1^{\ast }\setminus {\sigma }_2^{\ast })\cap S)/4$.

By Theorem 3, we can compute $\tilde{w}$ such that $w^{\ast }\le \tilde{w}\le 10w^{\ast }$ in $O(n)$ time.

Consider a slab ${\sigma }_0^{\ast }$ that has the same orientation as ${\sigma }_1^{\ast }$, has width $w^{\ast }$, and contains ${\sigma }_1^{\ast }$. In particular, if $w({\sigma }_1^{\ast })=w^{\ast }$, then ${\sigma }_0^{\ast }$ is ${\sigma }_1^{\ast }$.

Observe that $P=S\cap ({\sigma }_1^{\ast }\setminus {\sigma }_2^{\ast })$ and ${\sigma }_0^{\ast }$ satisfy the four conditions in the statement of Lemma 5 for $(p,q)$ and the value $\tilde{w}$ computed above, with $c=10$. Therefore, in $O(1/\epsilon )$ time, we can compute a set $\mathrm{\Gamma }$ of $O(1/\epsilon )$ orientations such that there exists a slab ${\sigma }^{\prime }$ with orientation $\gamma \in \mathrm{\Gamma }$ that covers $S\cap ({\sigma }_1^{\ast }\setminus {\sigma }_2^{\ast })$ and satisfies $w({\sigma }^{\prime })\le (1+\epsilon )w^{\ast }$. This implies that there exists a pair of slabs whose union covers $S$, one of which has an orientation from $\mathrm{\Gamma }$, and whose maximum width is at most $(1+\epsilon )w^{\ast }$.

For every $\gamma \in \mathrm{\Gamma }$, we find a pair of slabs whose union covers $S$, one of which has orientation $\gamma$, and whose maximum width is minimized. By Theorem 11, this can be done in $O((n/\epsilon )\log n)$ time in total. We repeat this procedure for every pair in $F$, which adds only a constant factor to the running time. Observe that each of the pairs of slabs we obtain has the property that its union covers $S$. Among these pairs, we output the one with the smallest maximum width. Thus, we conclude the following lemma.

To further refine the logarithmic term, we compute an $\epsilon$-certificate $Q$ of $S$ (see Section 3.3). By Theorem 6, this can be done in $O(n)$ time and $|Q|=O(1/{\epsilon }^2)$. We then compute a $(1+\epsilon )$-approximate pair $({\sigma }_1,{\sigma }_2)$ for the general two-line-center problem on $Q$, which can be done in $O((|Q|/\epsilon )\log |Q|)$ time by Lemma 13. Without loss of generality, we assume that ${\sigma }_1$ and ${\sigma }_2$ have the same width (otherwise, we expand the smaller one). Let $w=w({\sigma }_1)=w({\sigma }_2)$. Since $Q\subseteq S$, it is clear that $w\le (1+\epsilon )w^{\ast }$.

Let $({\sigma }_1^{\prime },{\sigma }_2^{\prime })$ be the pair of slabs obtained by taking the $\epsilon$-expansions of ${\sigma }_1$ and ${\sigma }_2$, respectively. By definition, ${\sigma }_1^{\prime }\cup {\sigma }_2^{\prime }$ covers $S$, and $w({\sigma }_1^{\prime })=w({\sigma }_2^{\prime })\le {(1+\epsilon )}^2{w}^{\ast }\le (1+3\epsilon )w^{\ast }$.

The total running time is $O(n+(\mu /\epsilon )\log \mu )$, where $\mu =\min \{n,\mathrm{\hspace{0.17em}1}/{\epsilon }^2\}$, which can also be expressed as both $O((n/\epsilon )\log (1/\epsilon ))$ and $O(n+(1/{\epsilon }^3)\log (1/\epsilon ))$. By replacing $\epsilon$ with $\epsilon /3$, we obtain the following theorem.