wu :: forums « wu :: forums - Bitonic Tours » Welcome, Guest. Please Login or Register. Apr 18th, 2024, 3:43pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: towr, SMQ, Eigenray, Icarus, ThudnBlunder, Grimbal, william wu)    Bitonic Tours « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Bitonic Tours  (Read 1536 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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »