wu :: forums
« wu :: forums - Bitonic Tours »

Welcome, Guest. Please Login or Register.
Dec 11th, 2024, 10:12am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: SMQ, Icarus, Grimbal, ThudnBlunder, towr, william wu, Eigenray)
   Bitonic Tours
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Bitonic Tours  (Read 1551 times)
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Bitonic Tours  
« on: Feb 7th, 2003, 1:36pm »
Quote Quote Modify 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 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...
IP Logged

Doc, I'm addicted to advice! What should I do?
Rezyk
Junior Member
**





   
Email

Gender: male
Posts: 85
Re: Bitonic Tours  
« Reply #1 on: Nov 11th, 2003, 8:37pm »
Quote Quote Modify 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 sub-questions of the same form.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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