Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to write a rank function in math for this problem?

Initially: there are 2n points on the Euclidean plane. The points are grouped in pairs with a line segment connecting each pair.

Action: the following untangling operation is repeatedly applied to the points.

Note that new pairs of crossed line segments may result from this operation.

Question: will this process terminate?

The process will terminate because we can choose 4 point randomly which two lines are tangling and then untangle them. the sum of line's length will decrease every untangle action. the sum of line's length will finally decrease to an unknown number and process terminated.

edit: untangling operation is choose four points that two lines are cross over, and then untangle them, so that the new lines aren't tangling. for example there are four points A, B, C, D that connect Line AB and CD as like "X". the untangle process rearrange the connecting points which create new line AC and BD, and they are not cross (untangle), it look like "||"

share|improve this question
4  
what untangling operation? –  Bhargav Oct 5 '11 at 7:55
    
untangling operation is choose four points that two lines are cross over, and then untangle them, so that the new lines aren't tangling. for example there are four points A, B, C, D that connect Line AB and CD as like "X". the untangle process rearrange the connecting points which create new line AC and BD, and they are not cross (untangle), it look like "||" –  Byron0324 Oct 5 '11 at 15:46
2  
What is a rank function? –  Mike Spivey Oct 5 '11 at 17:20
add comment

1 Answer

The question is very unclear to me, so my answer may be off base. You can use the total length of the line segments as a rank function. As you note, this decreases each time you do an untangle. Moreover, since there are only finitely many ways of drawing the line segments, there are only finitely many values of the rank function, one of which is the minimum value. So each untangle reduces the rank, and after finitely many untangles you must reach the minimum rank, and there are no more untangles left to do.

Are you asking for a formula for the sum of the lengths of the line segments?

By the way, this is very closely related to Problem A4 on the 1979 Putnam exam. I'm sure you can find that exam, with solutions, somewhere on the web.

share|improve this answer
    
This argument is often used to prove that a solution to the Euclidean TSP is a simple polygon. This was first observed by Flood in 1956 (Operations Res. 4, 61–75; MR0078639). –  lhf Oct 6 '11 at 2:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.