Author |
Topic: Bitonic Tours (Read 1551 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
 |
Bitonic Tours
« on: Feb 7th, 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 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
Gender:
Posts: 85
|
|
Re: Bitonic Tours
« Reply #1 on: Nov 11th, 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 sub-questions of the same form.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print