2026-09-10T09:44:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27723 2026-09-09T12:19:35Z ddc:004 open_access

Bichromatic Geometric Spanners Fung, Theodore Tóth, Csaba D. Euclidean spanner bichromatic points computational geometry For an edge-weighted graph G = (V,E) and a stretch parameter t ≥ 1, a t-spanner is a subgraph H ⊆ G such that the shortest path distances in G and H satisfy δ_H(u,v) ≤ t δ_G(u,v) for all u,v ∈ 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 ε > 0, there is an (1+ε)-spanner with O(n/ε) edges (the stretch can be arbitrarily close to 1). When G = K(R,B) is the complete bipartite graph on n bichromatic points in the plane, in general, no spanner construction can achieve stretch t < 3 with o(n²) edges. Bose et al. (SICOMP 2009) constructed a (3+ε)-spanner with O(nlog n) edges for any constant ε > 0. Our main result is a new construction for a (3+ε)-spanner with O(√{1/ε} ⋅ n) edges. Eliminating the O(log n) factor resolves a problem left open for more than 17 years, and raises a new research problem about optimizing the dependence on ε. We also study spanners for G = K(R,B) on n bichromatic points on the real line: In this case, we show that the MST of K(R,B) is a 7-spanner, and we construct a 3-spanner with at most 2n-3 edges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Theodore Fung and Csaba D. Tóth 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.6 urn:nbn:de:0030-drops-277233 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode