One of the talks at CCCG was by Ahmad Biniaz, on

red-blue-purple spanning graphs: given a partition of a point set into red, blue, and purple points, find a minimum-weight graph such that the red-purple and blue-purple subsets induce connected subgraphs. It can be solved by

matroid intersection, but this is slow and Biniaz talked about a faster special case. Anyway, in his talk, Ahmad mentioned a different colored spanning problem: find a minimum spanning tree of the complete bipartite geometric graph determined by a set of red and blue points in the Euclidean plane (with no purple this time). He noted that bichromatic closest pairs can be used to solve it in time

*O*(

*n* log

^{8} *n*), and asked whether a faster algorithm is possible. The illustration below gives an example of this problem and its solution.

**( Read more...Collapse )**