Extreme Distances in Multicolored Point Sets

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.