{"id":"arxiv/2607.10062","url":"https://arxiv.org/abs/2607.10062","tags":["cs.CG","math.CO"],"score":0,"title":"Bichromatic Geometric Spanners","domain":"cs.CG","source":"arxiv","authors":["Theodore Fung","Csaba D. Tóth"],"reviews":0,"subject":"cs.CG","summary":"For an edge-weighted graph $G=(V,E)$ and a stretch parameter $t\\geq 1$, a $t$-spanner is a subgraph $H\\subseteq G$ such that the shortest path distances in $G$ and $H$ satisfy $δ_H(u,v)\\leq t\\, δ_G(u,v)$ for all $u,v\\in V$. In metric spanners, $V$ is a finite metric space, and $G$ is the complete graph with edge weights corresponding to the distances between the endpoints. When $G$ is the complete graph on $n$ points in the plane, $O(n)$-size $t$-spanners are possible for any $t>1$: For every $\\varepsilon>0$, there is an $(1+\\varepsilon)$-spanner with $O(n/\\varepsilon)$ edges (i.e., the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-11","reactions":{}}