An Improved Bound for Plane Covering Paths

We denote the convex hull of a point set $S$ by $\text{CH}(S)$. For two points $p$ and $q$ we denote by $\mathrm{\ell }(p,q)$ the line through $p$ and $q$, by $pq$ the line segment with endpoints $p$ and $q$, and by $\overrightarrow{pq}$ the ray that emanates from $p$ and passes through $q$. The concatenation of two paths, ${\delta }_1$ and ${\delta }_2$, that share an endpoint is denoted by ${\delta }_1\oplus {\delta }_2$.

Our algorithm is iterative and scans the points from left to right. Note that via a suitable rotation we may assume that no two points of $P$ have the same $x$-coordinate. In the first iteration we scan only one point. In each subsequent iteration except for the last, we scan $6$ or $7$ new points and cover them with $5$ or $6$ new segments, respectively. Thus the ratio of the number of new segments to the number of covered points in these intermediate iterations is at most $6/7$. In the last iteration we scan the (at most $6$) remaining points.

We assume that, among the scanned points in each iteration, no three are collinear. Collinear points are typically easier to handle because one can cover three points by one segment – such cases can be handled by an argument similar to that of [13]. Let $m$ represent the number of points that have been scanned so far and let $l^{\prime }$ represent the rightmost scanned point. We maintain the following invariant at the beginning of every iteration after the first.

All $m$ points that have been scanned so far are covered by a non-crossing path $\delta$ with at most $\lfloor 6m/7\rfloor$ segments. The path $\delta$ lies to the left of the vertical line through $l^{\prime }$. The degree of $l^{\prime }$ in $\delta$ is one if $m⩾2$ and zero if $m=1$.

The invariant holds after the first iteration, trivially. We now focus on how to handle each intermediate iteration; this is the main part of our algorithm and proof. The last iteration is described at the end. Note that the invariant has the floor-function, whereas Theorem 1 has the ceiling-function. As we will see, at the beginning of each iteration, the $m$ points scanned so far are covered by at most $\lfloor 6m/7\rfloor$ segments. After the last iteration, we have $m=n$ and this upper bound becomes $\lceil 6n/7\rceil$.

In each intermediate iteration the new points are appended to the current path $\delta$ in a suitable way, without altering the structure of $\delta$. In our descriptions we will use $\mathrm{\Delta }$ to denote the resulting path.

We start by scanning 6 new points. Denote these points by $l$, $a$, $b$, $c$, $r$, $r^{\prime }$, where $l$ is the leftmost, $r^{\prime }$ is the rightmost and $r$ is the second rightmost point, as in Figure 2. Let $S=\{l,a,b,c,r\}$. Thus, $S$ has all newly scanned points except for $r^{\prime }$. Let $L$ and $R$ be the vertical lines through $l$ and $r$, respectively. We refer to the region between $L$ and $R$ as the slab. Observe that $l$ and $r$ are both vertices of the boundary of $\text{CH}(S)$. We consider three cases depending on the number of vertices on $\text{CH}(S)$.

$\text{CH}(S)$ has 3 vertices. Without loss of generality, assume that $a$ is the third vertex of $\text{CH}(S)$, located below $\mathrm{\ell }(l,r)$. Thus $b$ and $c$ are inside triangle $△(a,l,r)$. The line $\mathrm{\ell }(b,c)$ intersects exactly two edges of $△(a,l,r)$. We consider three subcases.

• $\mathrm{■}$

  $\mathrm{\ell }(b,c)$ intersects $\mathrm{\ell }(l,r)$ and $ar$, as shown in Figure 2(a). The points $l$, $b$, $c$, and $a$ form the vertices of a convex quadrilateral. After a suitable relabeling, we may assume that they appear in this order along the boundary of the quadrilateral. Then the intersection $x$ of $\mathrm{\ell }(a,c)$ and $\mathrm{\ell }(l,b)$ lies in $△(a,l,r)$. We form the path path $(l^{\prime },l,x,a,r,r^{\prime })$ and append it to $\delta$. Thus we cover the six new vertices $(l,b,c,a,r,r^{\prime })$ with five segments. The savings come from avoiding using segment $bc$.

• $\mathrm{■}$

  $\mathrm{\ell }(b,c)$ intersects $lr$ and $al$. This is symmetric to the previous case. We let $l^{\prime }$ and $l$ play the role of $r^{\prime }$ and $r$. Points $a,b,c,r$ form a convex quadrilateral, and we create the path $(l^{\prime },l,a,x,r,r^{\prime })$.

• $\mathrm{■}$

  $\mathrm{\ell }(b,c)$ intersects $al$ and $ar$. We may assume, without loss of generality, that $b$ is to the left of $c$. Then $\overrightarrow{ab}$ intersects $L$ or $\overrightarrow{ac}$ intersects $R$. Because of symmetry, assume that $\overrightarrow{ab}$ intersects $L$. Their intersection, $y$, must be above $l$. Denote by $y^{\prime }$ the intersection point of $\mathrm{\ell }(b,c)$ with $L$, as in Figure 2(b). Observe that $y^{\prime }$ is below $l$. In this setting $\overrightarrow{l^{\prime }l}$ intersects either $by$ or $b{y}^{\prime }$, at a point $u$. If $\overrightarrow{l^{\prime }l}$ intersects $by$, we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },u,a,c,r,r^{\prime })$ as in Figure 2(b), otherwise we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },u,c,a,r,r^{\prime })$ as in Figure 2(c). Either way we cover 6 vertices with 5 segments, by avoiding $lb$ on our path.

$\text{CH}(S)$ has 5 vertices (i.e., $l$, $a$, $b$, $c$, $r$). By reflection and relabeling, there are two subcases to consider.

• $\mathrm{■}$

  The three vertices $a$, $b$, and $c$ lie on the same side of $lr$ (wlog below). We may assume that they appear in the order $a,b,c$ from left to right; see Figure 3(a). Then the intersection point $x$ of $\mathrm{\ell }(l,a)$ and $\mathrm{\ell }(b,c)$ lies in the slab. We set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,x,c,r,r^{\prime })$.

• $\mathrm{■}$

  Two vertices, say $a$ and $b$, lie on one side of $lr$ (wlog below), and $c$ lies on the other side. Assume that $a$ is to the left of $b$. The intersection, $u$, of $\mathrm{\ell }(l,a)$ and $\mathrm{\ell }(r,b)$ must be in the slab, by convexity. If $l^{\prime }$ is above $\mathrm{\ell }(l,c)$ then we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },c,l,u,r,r^{\prime })$, as shown in Figure 3(b). Symmetrically, if $r^{\prime }$ is above $\mathrm{\ell }(r,c)$, we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,u,r,c,r^{\prime })$.
  Finally if $l^{\prime }$ is below $\mathrm{\ell }(l,c)$ and $r^{\prime }$ is below $\mathrm{\ell }(r,c)$, let $v$ be the intersection point of $\mathrm{\ell }(l^{\prime },l)$ and $\mathrm{\ell }(r,c)$; see Figure 3(c). By convexity, $v$ is in the slab, so we can set $\mathrm{\Delta }=\delta \oplus (l^{\prime },v,r,a,b,r^{\prime })$.

$\text{CH}(S)$ has 4 vertices: $l,r,a,b$. We consider two subcases.

$a$ and $b$ lie on different sides of $lr$. Wlog, $a$ is below. The point $c$ lies either in triangle $△(a,b,l)$ or in triangle $△(a,b,r)$. The configurations are symmetric so we show how to handle the former. It is implied that $c$ is to the left of $\overrightarrow{ab}$, which in turn implies that at least one of $\overrightarrow{ac}$ or $\overrightarrow{bc}$ intersects $L$. Wlog, assume that $\overrightarrow{ac}$ intersects $L$. The intersection point, $y$, must be above $l$. There are two subcases to consider:

• $\mathrm{■}$

  $\overrightarrow{bc}$ intersects $L$, at point $y^{\prime }$, which must be below $l$. Then either $\overrightarrow{l^{\prime }l}$ intersects $cy$ as in Figure 4(a), or it intersects $c{y}^{\prime }$ as in Figure 4(b). Either way, let the intersection point be $x$. Respectively, we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },x,a,b,r,r^{\prime })$ or we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },x,b,a,r,r^{\prime })$.

• $\mathrm{■}$

  $\overrightarrow{bc}$ intersects $R$, as in Figure 4(c). In this case the intersection point $u$ of $\mathrm{\ell }(b,c)$ and $\mathrm{\ell }(r,a)$ lies in the slab. We set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,b,u,r,r^{\prime })$.

$a$ and $b$ are on the same side of $lr$, (wlog, below; and also $a$ is to the left of $b$). By convexity, the intersection point, $x$, of $\mathrm{\ell }(l,a)$ and $\mathrm{\ell }(r,b)$ is in the slab. If $l^{\prime }$ lies above $\mathrm{\ell }(l,c)$, as in Figure 5(a), we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },c,l,x,r,r^{\prime })$. Symmetrically, if $r^{\prime }$ lies above $\mathrm{\ell }(r,c)$, then we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,x,r,c,r^{\prime })$. It remains to consider the case when $l^{\prime }$ is below $\mathrm{\ell }(l,c)$ and $r^{\prime }$ is below $\mathrm{\ell }(r,c)$. We consider two subcases.

• $\mathrm{■}$

  $\overrightarrow{bc}$ intersects $al$, as in Figure 5(b). In this case, the intersection point $u$ of $\overrightarrow{lc}$ and $\overrightarrow{rb}$ is in the slab because $c$ is to the right of $l$, and $b$ is to the left of $r$. Moreover, since $l$ is above $\overrightarrow{bc}$, $u$ does not lie on either of the segments $lc$ and $rb$. We set $\mathrm{\Delta }=\delta \oplus (l^{\prime },a,l,u,r,r^{\prime })$. Symmetrically, if $\overrightarrow{ac}$ intersects $br$ we can set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,u,r,b,r^{\prime })$, but this does not seem to help or simplify the next case.

• $\mathrm{■}$

  $\overrightarrow{bc}$ does not intersect $al$. In this case $\overrightarrow{bc}$ lies in the wedge with counterclockwise boundary ray $\overrightarrow{bl}$ and clockwise boundary ray $\overrightarrow{br}$. Because $l^{\prime }$ is below $\mathrm{\ell }(l,c)$ and $r^{\prime }$ is below $\mathrm{\ell }(r,c)$, it follows that $\overrightarrow{bc}$ intersects at least one of the rays $\overrightarrow{l^{\prime }l}$ and $\overrightarrow{r^{\prime }r}$ within the slab. If the intersection is with $\overrightarrow{r^{\prime }r}$ then the intersection point $z$ must be inside the shaded region in Figure 5(c), i.e., above $lr$ or in the triangle $△(l,c,r)$. Accordingly, we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,a,b,z,r^{\prime })$. Otherwise, let $z$ be the intersection of $\overrightarrow{bc}$ with $\overrightarrow{l^{\prime }l}$. This is the case when we need to scan a new point.
  Let $r^{\prime \prime }$ be the next point, after $r^{\prime }$. If $r^{\prime \prime }$ is below $\mathrm{\ell }(r,r^{\prime })$, then the intersection point $v$ of $\mathrm{\ell }(b,r)$ and $\mathrm{\ell }(r^{\prime \prime },r^{\prime })$ is in the vertical slab between $r$ and $r^{\prime }$; we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,a,c,b,v,r^{\prime \prime })$ as in Figure 5(d). Otherwise, $r^{\prime \prime }$ is above $\mathrm{\ell }(r,r^{\prime })$. Now if $r^{\prime }$ is above $\mathrm{\ell }(a,b)$, then the intersection point $w$ of $\mathrm{\ell }(l,a)$ and $\mathrm{\ell }(r^{\prime },b)$ lies in the slab, below $\mathrm{\ell }(a,b)$; we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },l,w,r^{\prime },c,r,r^{\prime \prime })$ as in Figure 5(e). Because $r^{\prime }$ is below $\mathrm{\ell }(c,r)$, $c{r}^{\prime }$ does not intersect $r{r}^{\prime \prime }$. If $r^{\prime }$ is below $\mathrm{\ell }(a,b)$, we set $\mathrm{\Delta }=\delta \oplus (l^{\prime },z,b,a,r^{\prime },r,r^{\prime \prime })$ as in Figure 5(f). In each case we cover seven new points (including $r^{\prime \prime }$) with six edges.

This is the end of an intermediate iteration. In each case, we append to $\delta$ a non-crossing path that lies in the vertical slab between $l$ and the rightmost scanned point. Thus $\mathrm{\Delta }$ is non-crossing. Moreover the degree of the rightmost point in $\mathrm{\Delta }$ (which is $r^{\prime }$ or $r^{\prime \prime }$) is one. In each case we have scanned 6 or 7 new points and covered them by 5 or 6 new segments, respectively. If we have scanned $6$ points, then the total number $M$ of scanned points is $M=m+6$, and the number of segments of $\mathrm{\Delta }$ is

If we have scanned $7$ points, then $M=m+7$, and we have

Therefore, the invariant holds after every intermediate iteration.

In the last iteration of the algorithm we are left with $n^{\prime }$ points where $1⩽n^{\prime }⩽6$. We cover these points by an $x$-monotone path with $n^{\prime }-1$ segments and connect it to the rightmost scanned point (of the path that has been constructed so far) by an additional segment. This gives a non-crossing covering path for all points. The total number of segments in this path is at most

Each iteration takes $O(1)$ time. Therefore, after rotating and sorting the points in $O(n\log n)$ time, the rest of the algorithm takes $O(n)$ time. This concludes the proof of Theorem 1.