wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> cs >> Bitonic Tours
(Message started by: James Fingas on Feb 7th, 2003, 1:36pm)

Title: Bitonic Tours
Post by James Fingas on Feb 7th, 2003, 1:36pm
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 bottom-most 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...

Title: Re: Bitonic Tours
Post by Rezyk on Nov 11th, 2003, 8:37pm
Hint 1: [hide]"Given points A and B, what is the optimal 'bitonic path' that has them as endpoints and crosses every point leftward of them?"[/hide]

Hint 2: [hide]Don't try to answer the question in hint 1 explicitly.  Answer it using sub-questions of the same form.[/hide]



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board