Here is a problem described to me by fakalin. Given n red points and n blue points, no three of which are collinear, prove that there exists a pairing of red and blue points such that the line segments connecting each pair do not intersect.<\/p>\n
<\/p>\n
The solution is straightforward though it took a while to identify after it was already staring me in the face.<\/p>\n
With each pairing is associated a total length (sum of line segment lengths). Since there are a finite number of pairings, there is a minimum length pairing. We claim this pairing must be one that satisfies the problem statement.<\/p>\n
Suppose it were not, then there are some 2 red and 2 blue points such that the pairs’ connecting line segments cross. Then uncross the two pairs. This can be done because the points are not collinear. By uncrossing, the sum of the pairs’ segment lengths strictly decreases and therefore the total length also decreases. This contradicts the supposition. Therefore the claim is true.<\/p>\n
However, note that a pairing that satisfies the statement need not be minimum total length. (The minimum total length doesn’t even need to be unique.) Nevertheless, an algorithm for reaching a solution is to start with any pairing, then identify any crossed pairs and uncross them. During this process, crossed pairs count may even increase for a time, but total length always decreases strictly at each step. Therefore, the algorithm will terminate, either when a valid pairing is reached, or when the minimum total length is reached, which also gives a valid pairing.<\/p>\n
An extended question is, given the valid pairing, can a non-self-intersecting red-blue alternating path connecting all the points be found? I believe the answer is yes.<\/p>\n","protected":false},"excerpt":{"rendered":"
Here is a problem described to me by fakalin. Given n red points and n blue points, no three of which are collinear, prove that there exists a pairing of red and blue points such that the line segments connecting each pair do not intersect.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[238,235,233,232,231,236,237,230,239,234],"class_list":["post-185","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-collinear","tag-face","tag-finite-number","tag-line-segment","tag-line-segments","tag-pair","tag-segment","tag-segment-lengths","tag-sum","tag-supposition"],"_links":{"self":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/185","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=185"}],"version-history":[{"count":0,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/185\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}