Author 
Topic: Bitonic Tours (Read 1502 times) 

James Fingas
Uberpuzzler
Gender:
Posts: 949


Bitonic Tours
« on: Feb 7^{th}, 2003, 1:36pm » 
Quote Modify

Okay, I've got one observation to start this problem off: it is never valuable for the first leg of the trip to cross the second leg of the trip, so we can say for certain that the topmost point is on the first leg of the trip, and the bottommost point is on the second leg. However, these could be the leftmost and rightmost points, respectively. But if we are trying to add any point above the convex hull of the first leg, we should add it to the first leg, and if we are trying to add any point below the convex hull of the second leg, we should add it to the second leg. Therefore, we can start by forming the convex hull of the entire set of points. All points on the top face of this convex hull must be on the first leg, and all points on the bottom of the convex hull must be on the second leg. The inner points will be decided later. Maybe we could start with the convex hull, and measure each point in its absolute vertical distance from the top and bottom of the hull. If we always add the point with the smallest absolute distance, maybe we'll get the right answer? Maybe? Well, at least it's a start...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Rezyk
Junior Member
Gender:
Posts: 85


Re: Bitonic Tours
« Reply #1 on: Nov 11^{th}, 2003, 8:37pm » 
Quote Modify

Hint 1: "Given points A and B, what is the optimal 'bitonic path' that has them as endpoints and crosses every point leftward of them?" Hint 2: Don't try to answer the question in hint 1 explicitly. Answer it using subquestions of the same form.


IP Logged 



