4 problems

For $1<p\leq 2$, consider geometric spanners for finite subsets of $\ell_p$ with stretch $t$. Geometric spanner optimality conjecture. Tight instances exist in these spaces; that i…

Given a point set in the plane, its $L_2$-Delaunay graph is the classical Euclidean Delaunay graph. The stretch of a plane spanner is the maximum, over pairs of vertices, of the ra…

Let $G$ be the lighter degree-$3$ spanner of the infinite square lattice shown in Fig., and let $\delta_0$ denote the minimum stretch factor for degree-$3$ spanners of the lattice.…

Let $\Lambda$ be the infinite square lattice, and let $\delta_0(\Lambda,3)$ denote its minimum stretch factor among degree-$3$ spanners. Degree 3 dilation conjecture. … The paper h…