Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00080 Extreme Distances in Multicolored Point Sets Adrian Dumitrescu and Sumanta Guha 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.
|
Revised: March 2004. Submitted: January 2003. Communicated by Michael Goodrich |
| Journal of Graph Algorithms and Applications |