MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points (in my application, the distances are Manhattan/$L_1$).

For example, given the locations of US cities, we would find an MST that connects to one city from every state.

If helpful, we could additionally assume that the local density of the pointset is upper-bounded (the points can't be clustered too closely). Points of the same color will generally come in groups (can even assume that each color corresponds to a connected region).

A straightforward heuristic would average locations of points of each color, build an MST for those "centers", and then look for shortcuts. Is there something better ?

Points of interest: a proof of NP-hardness, an approximation algorithm, an effective heuristic

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.