Yao-Yao Graph a Spanner?

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $S\subset\mathbb R^2$ be finite and fix $k$ equally spaced ray directions. Translate the resulting $k$ cones to each $u\in S$. The directed Yao graph $Y_k$ selects, in each nonempty cone at $u$, a shortest outgoing edge $u\to v$. To form $YY_k$, at each vertex and in each cone retain only the shortest incoming edge from that cone, then forget the edge orientations. Use a consistent convention for boundary rays and equal distances. A geometric graph is a $t$-spanner if its shortest Euclidean-edge-length path distance satisfies $d_G(u,v)\le t\lVert u-v\rVert$ for every pair.

Statement recorded in the supplied source.

For which fixed cone counts $k$ is the Yao--Yao graph $YY_k$ a $t$-spanner with a constant $t$ independent of the finite point set? This records the source's question for the family $YY_k$, allowing the constant to depend on $k$. [S2]

Short English statement

For which fixed cone counts $k$ is the Yao--Yao graph $YY_k$ a $t$-spanner with a constant $t$ independent of the finite point set? This records the source's question for the family $YY_k$, allowing the constant to depend on $k$.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 5500070 (AMR-054-0070). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke (editors), The Open Problems Project, maintained original source, Problem 70, Statement and complete Partial/Related Results. https://github.com/edemaine/topp/blob/main/Problems/P.000070.