2 papers
cs.CG2024
Minimum Plane Bichromatic Spanning Trees
Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine +3
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endp…
cs.CG2024
Towards Instance-Optimal Euclidean Spanners
Hung Le, Shay Solomon, Cuong Than +2
Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic "compactness'' measures of a Euclidean spanner are the…