Given a set of *n* red points and *n* blue points in the plane, we are interested to match the red points with the blue points by straight line segments in such a way that the segments do not cross each other and the length of the longest segment is minimized. In general, this problem in NP-hard. We give exact solutions for some special cases of the input point set.

This is joint work with Anil Maheshwari and Michiel Smid.

Let *S* be a finite set of points on the unit-sphere *S*^{2}. In 1987, Raghavan suggested that the convex hull of *S* is a Euclidean *t*-spanner, for some constant *t*. We prove that this is the case for *t* = 3 π (π/2 + 1)/2.

Our proof consists of generalizing the proof of Dobkin et al. from the Euclidean Delaunay triangulation to the spherical Delaunay triangulation.