Narrow Results

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem.

1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.

2. Each embedding of a closed convex curve has dilation ≥ 1.00157.

3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation .

We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem remains NP-hard even when a minimum-dilation tour or path is sought; not even an FPTAS exists in this case.

The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L₁ plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log² n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ ≥ 2 vectors and a worst-case O(n log^d n) time algorithm to d ≥ 3 dimensions in L₁-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log^d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L₁ plane.

(I) We exhibit a set of 23 points in the plane that has dilation at least $1.4308$, improving the previous best lower bound of $1.4161$ for the worst-case dilation of plane spanners.

(II) For every $n\ge 13$, there exists an $n$-element point set $S$ such that the degree $3$ dilation of $S$ equals $1+\sqrt{3}=2.7321\dots$ in the domain of plane geometric spanners. In the same domain, we show that for every $n\ge 6$, there exists a an $n$-element point set $S$ such that the degree $4$ dilation of $S$ equals $1+\sqrt{(5-\sqrt{5})/2}=2.1755\dots$ The previous best lower bound of $1.4161$ holds for any degree.

(III) For every $n\ge 6$, there exists an $n$-element point set $S$ such that the stretch factor of the greedy triangulation of $S$ is at least $2.0268$.

We present tight bounds on the spanning ratio of a large family of ordered $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta =2\pi /m$. An ordered $\theta$-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer $k\ge 1$, ordered $\theta$-graphs with $4k+4$ cones have a tight spanning ratio of $1+2sin(\theta /2)/(cos(\theta /2)-sin(\theta /2))$. We also show that for any integer $k\ge 2$, ordered $\theta$-graphs with $4k+2$ cones have a tight spanning ratio of $1/(1-2sin(\theta /2))$. We provide lower bounds for ordered $\theta$-graphs with $4k+3$ and $4k+5$ cones. For ordered $\theta$-graphs with $4k+2$ and $4k+5$ cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered $\theta$-graphs have worse spanning ratios than unordered $\theta$-graphs. Finally, we show that, unlike their unordered counterparts, the ordered $\theta$-graphs with 4, 5, and 6 cones are not spanners.

We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region, and origin-destination node pairs correspond to pairs of points in that region. The objective is to define a routing policy that assigns a continuous path to each origin-destination pair while minimizing the traffic, or load, passing through any single point. While the average load is minimized by straight-line routing, such a routing policy distributes the load non-uniformly, resulting in higher load near the center of the region. We consider one-turn rectilinear routing policies that divert traffic away from regions of heavier load, resulting in up to a 33% reduction in the maximum load while simultaneously increasing the path lengths by an average of less than 28%. Our policies are simple to implement, being both local and oblivious. We provide a lower bound that shows that no one-turn rectilinear routing policy can reduce the maximum load by more than 39% and we give a polynomial-time procedure for approximating the optimal randomized policy.

Let ${\delta }_0(P,k)$ denote the degree $k$ dilation of a point set $P$ in the domain of plane geometric spanners. If $\mathrm{\Lambda }$ is the infinite square lattice, it is shown that $1+\sqrt{2}\le {\delta }_0(\mathrm{\Lambda },3)\le (3+2\sqrt{2})5^{-1/2}=2.6065\dots$ and ${\delta }_0(\mathrm{\Lambda },4)=\sqrt{2}$. If $\mathrm{\Lambda }$ is the infinite hexagonal lattice, it is shown that ${\delta }_0(\mathrm{\Lambda },3)=1+\sqrt{3}$ and ${\delta }_0(\mathrm{\Lambda },4)=2$. All our constructions are planar lattice tilings constrained to degree $3$ or $4$.

In this short note, we prove that the degree-three dilation of the square lattice ${\mathbb{Z}}^2$ is $1+\sqrt{2}$. This disproves a conjecture of Dumitrescu and Ghosh. We give a computer-assisted proof of a local-global property for the uncountable set of geometric graphs achieving the optimal dilation.