Extreme Distances in Multicolored Point Sets
Vol. 8, no. 1, pp. 27-38, 2004. Regular paper.
Abstract Given a set of n colored points in some d-dimensional Euclidean space, a bichromatic closest (resp. farthest) pair is a closest (resp. farthest) pair of points of different colors. We present efficient algorithms to maintain both a bichromatic closest pair and a bichromatic farthest pair when the the points are fixed but they dynamically change color. We do this by solving the more general problem of maintaining a bichromatic edge of minimum (resp. maximum) weight in an undirected weighted graph with colored vertices, when vertices dynamically change color. We also give some combinatorial bounds on the maximum multiplicity of extreme bichromatic distances in the plane.
Submitted: January 2003.
Revised: March 2004.
Communicated by Michael T. Goodrich
article (PDF)