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 S2. 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.