Computing shortest heterochromatic monotone routes

Given a set of n points on the plane colored with k≤n colors, the Trip Planning Problem asks for the shortest path visiting the k colors. It is a well-known NP-hard problem. We show that under some natural constraints on the path, the problem can be solved in polynomial time.