Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00080
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.
|
Journal Supporters
|