Generalized Sweeping Line Spanners

A geometric graph $G$ is a graph whose vertices are points in the plane and whose edges are line segments between pairs of points. Every edge in the graph has weight equal to the Euclidean distance between its two endpoints. The distance between two vertices $u$ and $v$ in $G$, denoted by $\delta_{G}(u,v)$, or simply $\delta(u,v)$ when $G$ is clear from the context, is defined as the sum of the weights of the edges along a shortest path between $u$ and $v$ in $G$. A subgraph $H$ of $G$ is a $t$-spanner of $G$ (for $t\geq 1$) if for each pair of vertices $u$ and $v$, $\delta_{H}(u,v)\leq t\cdot\delta_{G}(u,v)$. The smallest $t$ for which $H$ is a $t$-spanner is the spanning ratio or stretch factor of $H$. The graph $G$ is referred to as the underlying graph of $H$ and, unless otherwise specified, this is assumed to be the complete Euclidean graph. The spanning properties of various geometric graphs have been studied extensively in the literature (see [10, 16] for an overview). The spanning ratio of a class of graphs is the supremum over the spanning ratios of all members of that graph class. Since spanners preserve the lengths of all paths up to a factor of $t$, these graphs have applications in the context of geometric problems, including motion planning and optimizing network costs and delays.

We introduce a generalization of an existing geometric spanner ($\Theta$-graphs) which we call sweeping line graphs. We show that these graphs are spanners, also when considering line segment obstacles or polygonal obstacles during their construction. We show this using a very general method that we conjecture applies to other geometric spanners as well, meaning that such proofs do not have to be reinvented for different spanner constructions.

Clarkson [12] and Keil [15] independently introduced $\Theta$-graphs as follows: for each vertex $u$, we partition the plane into $k$ disjoint cones with apex $u$. Each cone has aperture equal to $\theta=\frac{2\pi}{k}$ (see Figure 2) and the orientation of these cones is identical for every vertex. The $\Theta$-graph is constructed by, for each cone with apex $u$, connecting $u$ to the vertex $v$ whose projection onto the bisector of the cone is closest to $u$ (see Figure 2). When $k$ cones are used, we denote the resulting $\Theta$-graph as the $\Theta_{k}$-graph. We note that while $\Theta$-graphs can be defined using an arbitrary line in the cone instead of the bisector (see Chapter 4 of [16]), the bisector is by far the most commonly used construction and the spanning ratios mentioned in the following paragraph only apply when the bisector is used in the construction process.

Ruppert and Seidel [17] upperbounded the spanning ratio of these graphs (when there are at least 7 cones) by $1/(1-2\sin(\theta/2))$, when $\theta<\pi/3$. Bonichon et al. [3] showed that the $\Theta_{6}$-graph has a tight spanning ratio of 2, i.e., it has a matching upper and lower bound of 2. Other recent results include a tight spanning ratio of $1+2\sin(\theta/2)$ for $\Theta$-graphs with $4m+2$ cones, where $m\geq 1$ and integer, and improved upper bounds for the other families of $\Theta$-graphs [5]. When there are fewer than 6 cones, most inductive arguments break down. Hence, it was only during the last decade that upper bounds on the spanning ratio of the $\Theta_{5}$-graph and the $\Theta_{4}$-graph were determined: $\sqrt{50+22\sqrt{5}}\approx 9.960$ for the $\Theta_{5}$-graph [9] and $(1+\sqrt{2})\cdot(\sqrt{2}+36)\cdot\sqrt{4+2\sqrt{2}}\approx 237$ for the $\Theta_{4}$-graph [2]. These bounds were recently improved to $5.70$ for the $\Theta_{5}$-graph [8] and $17$ for the $\Theta_{4}$-graph [4]. Constructions similar to those demonstrated by El Molla [14] for Yao-graphs show that $\Theta$-graphs with fewer than 4 cones are not spanners. In fact, until recently it was not known that the $\Theta_{3}$-graph is connected [1].

An alternative way of describing the $\Theta$-graph construction is that for each cone with apex $u$, we visualize a line perpendicular to the bisector of the cone that sweeps outwards from the apex $u$. The $\Theta$-graph is then constructed by connecting $u$ to the first vertex $v$ in the cone encountered by the sweeping line as it moves outwards from $u$ (see Figure 4).

The sweeping line graph generalizes this construction by allowing the sweeping line to be at an angle $\gamma$ to the line perpendicular to the bisector of the cone (see Figure 4, a more precise definition follows in Section 2). When $\gamma\in[0,\frac{\pi-3\theta}{2})$ we show that the resulting graph is a spanner whose spanning ratio depends only on $\theta$ and $\gamma$. We note that this angle $\gamma$ implies that the line perpendicular to the sweeping line can be outside the cone associated with that sweeping line, which is not supported in the common $\Theta$-graph (using bisectors) or the more general ones described in [16]. For example, when 10 cones are used (i.e., $\theta=\pi/5$) the construction in [16] allows for an angle $\gamma$ up to $\theta/2=\pi/10$, while our construction allows the far larger value of $7\pi/20$ and this difference increases as the number of cones increases (i.e., $\theta$ decreases). The ability to rotate the sweeping line has previously been used to define ordered $\Theta$-graphs [7], where a sweeping line perpendicular to a cone boundary gave a more efficient construction method.

Pushing the generalization of these graphs even further, we consider spanners in two more general settings by introducing line segment constraints and polygonal obstacles. Specifically, given a set $P$ of points in the plane, let $S$ be a set of line segments connecting pairs of points in $P$ (not every vertex in $P$ needs to be an endpoint of a line segment in $S$). We refer to $S$ as line segment constraints, or simply constraints. The set of line segment constraints is planar, i.e. no two constraints intersect properly, but they can share endpoints. Two vertices $u$ and $v$ can see each other if and only if either the line segment $uv$ does not properly intersect any constraint or $uv$ is itself a constraint. If two vertices $u$ and $v$ can see each other, the line segment $uv$ is a visibility edge (this notion can be generalized to apply to arbitrary points that can see each other). The visibility graph of $P$ with respect to a set of constraints $S$, denoted by Vis$(P,S)$, has $P$ as vertex set and all visibility edges defined by vertices in $P$ as edge set. In other words, it is the complete graph on $P$ minus all edges that properly intersect one or more constraints in $S$. The aim of this generalization is to construct a spanner such that no edge of the spanner properly intersects any constraint. In other words, to construct a spanner of Vis$(P,S)$.

Polygonal obstacles generalize the notion of line segment constraints by allowing the constraints to be simple polygons instead of line segments, i.e., by excluding the internal area from being accessible. In this situation, $S$ is a finite set of simple polygonal obstacles where each corner of each obstacle is a point in $P$, such that no two obstacles intersect. We assume that each vertex is part of at most one polygonal obstacle and occurs at most once along its boundary, i.e., the obstacles are vertex-disjoint simple polygons, and no polygon contains any point of $P$ in its interior. Note that $P$ can also contain vertices that do not lie on the corners of the obstacles. The definitions of visibility edge and visibility graph are analogous to the ones for line segment constraints.

In the context of motion planning amid obstacles, Clarkson [12] showed how to construct a linear-sized $(1+\epsilon)$-spanner of Vis$(P,S)$. Subsequently, Das [13] showed how to construct a spanner of Vis$(P,S)$ with constant spanning ratio and constant degree. More recently, the constrained $\Theta_{6}$-graph was shown to be a 2-spanner of Vis$(P,S)$ [6] when considering line segment constraints. This result was recently generalized to polygonal obstacles [18]. Most related to this paper is the result by Bose and van Renssen [11], who generalized the results from Bose et al. [5] to the setting with line segment constraints, without increasing the spanning ratios of the graphs.

In this paper, we examine the sweeping line graph in the setting without constraints (or the unconstrained setting), with line segment constraints (or the constrained setting), and with polygonal obstacles. First, we generalize the spanning proof of the $\Theta$-graph given in the book by Narasimhan and Smid [16] to the sweeping line graph in the unconstrained setting. Next, we extend the proof to the constrained setting and finally apply it to the case of polygonal obstacles. In all three cases, we prove that the spanning ratio is upperbounded by $\frac{1}{\cos(\frac{\theta}{2}+\gamma)-\sin\theta}$, where $\theta=\frac{2\pi}{k}$ ($k\geq 7$) and $\gamma\in[0,\frac{\pi-3\theta}{2})$. The most interesting aspect of our approach is that the step from the unconstrained to the constrained and polygonal obstacle settings is very general and could apply to other spanner constructions in the unconstrained setting as well, making it a step towards a general condition of which spanners in the unconstrained setting can be proven to be spanners in the presence of obstacles.

Throughout this paper, the notation $|pq|$ refers to the Euclidean distance between $p$ and $q$. We also emphasize that a point can be any point in the plane, while a vertex is restricted to being one of the points in the point set $P$.

Before we formally define the sweeping line graph, we first need a few other notions. A cone is the region in the plane between two rays that emanate from the same point, called the apex of the cone. Let $k\geq 7$ and define $\theta=\frac{2\pi}{k}$. If we rotate the positive $x$-axis by angles $i\cdot\theta$, $0\leq i<k$, then we get $k$ rays. Each pair of consecutive rays defines a cone whose apex is at the origin. We denote the collection of these $k$ cones by $\zeta_{k}$. Let $C$ be a cone of $\zeta_{k}$. For any point $p$ in the plane, we define $C_{p}$ to be the cone obtained by translating $C$ such that its apex is at $p$.

Next, given an angle $\theta$ for a particular cone and an angle $\gamma\in[0,\frac{\pi-3\theta}{2})$, we give the definition of the sweeping line: For any vertex $x$ in a cone, let the sweeping line be the line through the vertex $x$ that is at an angle of $\gamma$ to the line perpendicular to the bisector of the cone. We then define $x_{\gamma}$ to be the intersection of the left-side of the cone and this sweeping line (see Figure 5).

Finally, we define the sweeping line graph:

In the remainder of the paper, we use $|ur_{\gamma}|$ when measuring the closeness between a vertex $r$ and the apex $u$ of a cone that contains it.

For ease of exposition, we only consider point sets in general position: no two vertices lie on a line parallel to one of the rays that define the cones, no two vertices lie on a line parallel to the sweeping line of any cone, and no three points are collinear. These assumptions can be removed using standard perturbation techniques.

We note that the construction time for the sweeping line graph is identical to that of the $\Theta$-graph: $O(n\log n)$ time. This can for example be achieved using the construction algorithm by Keil [15] and using the slanted sweepline instead of the perpendicular one (or alternatively rotating the point set).

Using the structure of the sweeping line graph, we define a simple algorithm called sweeping-routing to construct a path between any two vertices $s$ and $t$. The name comes from the fact that this is also a 1-local routing algorithm on the sweeping line graph. Let $t$ be the destination of the routing algorithm and let $u$ be the current vertex (initially $u=s$). If there exists a direct edge to $t$, follow this edge. Otherwise, follow the edge to the closest vertex in the cone of $u$ that contains $t$.

Now that we have our tools ready, it is time to prove that the sweeping line graph is a spanner in the unconstrained setting.

In addition to showing that the graph is a spanner, the above proof shows that the sweeping-routing algorithm constructs a bounded length path, thus we obtain a local competitive routing algorithm.

Next, we generalize the sweeping line graph to a more general setting with the introduction of line segment constraints. Recall that $P$ is a set of points in the plane and that $S$ is a set of line segments connecting two points in $P$ (not every point in $P$ needs to be an endpoint of a constraint in $S$, but a point in $P$ can be the endpoint of an arbitrary number of constraints). The set of constraints is planar, i.e. no two constraints intersect properly.

Let vertex $u$ be an endpoint of a constraint $c$ and let the other endpoint be $v$. Let $C$ be the cone of $\zeta_{k}$ such that $v\in C_{u}$. The line through $c$ splits $C_{u}$ into two subcones and for simplicity, we say that $v$ is contained in both of these. In general, a vertex $u$ can be an endpoint of several constraints and thus a cone can be split into several subcones (subcones are ordered in a clockwise fashion). For ease of exposition, when a cone $C_{u}$ is not split, we consider $C_{u}$ itself to be a single subcone. We use $C^{j}_{u}$ to denote the $j$-th subcone of $C_{u}$.

Recall that for any vertex $x$ in a cone, we defined $x_{\gamma}$ to be the intersection of the left-side of the cone and the sweeping line through $x$. We define the constrained sweeping line graph (see Figure 8):

To prove that the above graph is a spanner, we need three lemmas. A proof of Lemma 12 can be found in [6] (see also Figure 9).

The following lemma ensures that we can apply induction later.

We are now ready to prove that the constrained sweeping line graph is a spanner of the visibility graph.