{"id":745,"date":"2016-07-09T21:02:25","date_gmt":"2016-07-10T02:02:25","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=745"},"modified":"2016-07-20T21:52:39","modified_gmt":"2016-07-21T02:52:39","slug":"cutting-polygons-in-half","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/cutting-polygons-in-half\/","title":{"rendered":"Cutting polygons in half"},"content":{"rendered":"<p>This <a href=\"http:\/\/fivethirtyeight.com\/features\/can-you-save-riddler-headquarters-from-laser-larry-please\/\">Riddler puzzle<\/a> is about cutting polygons in half. Here is the problem:<\/p>\n<blockquote><p>\nThe archvillain Laser Larry threatens to imminently zap Riddler Headquarters (which, seen from above, is shaped like a regular pentagon with no courtyard or other funny business). He plans to do it with a high-powered, vertical planar ray that will slice the building exactly in half by area, as seen from above. The building is quickly evacuated, but not before in-house mathematicians move the most sensitive riddling equipment out of the places in the building that have an extra high risk of getting zapped.<\/p>\n<p>Where are those places, and how much riskier are they than the safest spots? (It\u2019s fine to describe those places qualitatively.)<\/p>\n<p>Extra credit: Get quantitative! Seen from above, how many high-risk points are there? If there are infinitely many, what is their total area?\n<\/p><\/blockquote>\n<p>Here is my solution:<br \/>\n<a href=\"javascript:Solution('soln_polycut','toggle_polycut')\" id=\"toggle_polycut\">[Show Solution]<\/a><\/p>\n<div id=\"soln_polycut\" style=\"display: none\">\n<h3>A note on interpretations<\/h3>\n<p>Because the problem doesn&#8217;t explain how to define &#8220;risk&#8221;, there are two main ways to interpret the problem.<\/p>\n<ol>\n<li>We can assume the laser cut will happen randomly, and the &#8220;risk&#8221; of a point is related to the likelihood that the cut will hit it. If the point is a geometrical point and the cut is infinitely thin, then all points have zero probability. If assume the point has a finite size, then the problem can make sense, but we still need to worry about <em>how the cuts are distributed<\/em>. For example:\n<ul>\n<li>we could start by choosing the angle of the cut uniformly at random and then pick the valid cut at this angle.<\/li>\n<li>we could randomly choose a point on the perimeter and then pick the valid cut that passes through that point.<\/li>\n<li>we could pick a point uniformly at random on the inside of the area and then choose a valid cut through that point.<\/li>\n<\/ul>\n<p>Each method will yield a different answer! This notion is related to <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bertrand_paradox_(probability)\">Bertrand&#8217;s Paradox<\/a>.<\/li>\n<li>Another way to interpret the problem is to avoid probability altogether and to count the number of different admissible cuts that can pass through a point and use this as a measure of how &#8220;unsafe&#8221; the point is.<\/li>\n<\/ol>\n<p>I chose interpretation #2 because it&#8217;s a well-defined problem that doesn&#8217;t require making additional assumptions. I&#8217;ll also present the solution to every polygon, because why not!<\/p>\n<h3>Even number of sides<\/h3>\n<p>Let&#8217;s start with an easy case. If the building is a square, or hexagon, or any other polygon with an even number of sides, then it&#8217;s clear by symmetry that all cuts will pass through the center of the polygon. See below for an illustration.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus46.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus46-1024x455.png\" alt=\"laser_locus46\" width=\"840\" height=\"373\" class=\"aligncenter size-large wp-image-777\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus46-1024x455.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus46-300x133.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus46-768x341.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus46-1200x533.png 1200w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus46.png 1544w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>We can all agree that the middle of the building is very unsafe, because <em>all cuts<\/em> go through it. Meanwhile, each other point in the building has precisely one possible cut passing through it. The same holds true if we have infinitely many sides (a circular building).<\/p>\n<h3>Odd number of sides<\/h3>\n<p>If the building is a polygon with an odd number of sides instead, such as a triangle or pentagon, then things get more interesting. It turns out that <strong>not all cuts through the center divide the area into equal halves<\/strong>. To understand why, take a look at the pentagon below with center at $P$ and short radius $|PA&#8217;| = 1$. Extend the top and bottom edges to meet at $O$ as shown. A similar figure can be drawn for any number of sides $n$. In any case, we&#8217;ll have $\\theta = \\tfrac{\\pi}{n}$.<br \/>\n<a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser1.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser1-1024x611.png\" alt=\"laser1\" width=\"840\" height=\"501\" class=\"aligncenter size-large wp-image-753\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser1-1024x611.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser1-300x179.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser1-768x458.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser1-1200x716.png 1200w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser1.png 1809w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>Clearly $AA&#8217;$ and $BB&#8217;$ are valid cuts because by symmetry they split the area of the pentagon in half. Suppose we&#8217;d like to make $XY$ a valid cut as well. Then it follows that the area $(OAA&#8217;)$ must equal the area $(OYX)$. Define the lengths $x = |OX|$ and $y = |OY|$. Then we must have:<\/p>\n<p>\\[<br \/>\nxy = |OA&#8217;||OA| = \\cot(\\tfrac{\\theta}{2})\\left( \\cot(\\tfrac{\\theta}{2}) + \\tan(\\theta) \\right) = \\cot^2(\\tfrac{\\theta}{2})\\sec(\\theta)<br \/>\n\\]<\/p>\n<p>If $P$ is the origin, the Cartesian coordinates of $X$ and $Y$ are<\/p>\n<p>\\[<br \/>\nX = \\begin{bmatrix}x \\,-\\, \\cot(\\tfrac{\\theta}{2}) \\\\ -1 \\end{bmatrix}<br \/>\n\\qquad<br \/>\nY = \\begin{bmatrix}y\\cos(\\theta) \\,-\\, \\cot(\\tfrac{\\theta}{2}) \\\\ y\\sin(\\theta) \\,-\\, 1 \\end{bmatrix}<br \/>\n\\]<\/p>\n<p>As $X$ slides from $A&#8217;$ to $B&#8217;$, $Y$ will slide from $A$ to $B$ in such a way that the product $xy$ remains constant. What we&#8217;d like to know is the shape of the curve that the line $XY$ traces out as it assumes all allowable configurations. One way to do this is to compute a parametric equation for the line $XY$. To do this, compute the vector $X + t(Y &#8211; X)$. Then, eliminate $y$ to obtain the following family of points:<\/p>\n<p>\\[<br \/>\nZ(x,t) = \\begin{bmatrix}<br \/>\n(1-t)x + \\frac{t}{x} \\cot^2(\\tfrac{\\theta}{2}) \\,-\\, \\cot(\\tfrac{\\theta}{2}) \\\\ -1 + \\frac{t}{x}\\cot^2(\\tfrac{\\theta}{2})\\tan(\\theta) \\end{bmatrix}<br \/>\n\\]<\/p>\n<p>Where $t \\in [0,1]$ and $x \\in [\\cot(\\tfrac{\\theta}{2}) ,\\cot(\\tfrac{\\theta}{2}) +\\tan(\\theta)]$. We don&#8217;t care about all of these points, however. We only want the boundary of the curve. To find it, fix one coordinate and maximize the other. e.g. let $\\eta = -1 + \\frac{t}{x}\\cot^2(\\tfrac{\\theta}{2})\\tan(\\theta)$, solve for $x$ in terms of $\\eta$ and $t$, substitute this into the first component of $Z(x,t)$, to obtain an expression that only depends on $\\eta$ and $t$. This will be a quadratic in $t$ that is maximized when $t=\\tfrac{1}{2}$. Therefore, the equation of the locus of points is simply $Z(x,\\tfrac{1}{2})$. If the polygon has $n$ sides, there will be $n$ such loci, each rotated about $P$ by an angle $\\frac{2k\\pi}{n}$, for $k=0,1,\\dots,n-1$. In the figure below, I plotted the result for the case $n=3,5,7$ (click to enlarge).<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus357.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus357.png\" alt=\"laser_locus357\" width=\"2128\" height=\"661\" class=\"aligncenter size-full wp-image-759\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus357.png 2128w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus357-300x93.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus357-768x239.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus357-1024x318.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_locus357-1200x373.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>Here are the diagrams repeated, but this time with some cuts drawn in and zoomed in to the middle portion (click to enlarge).<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_lines357.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_lines357.png\" alt=\"laser_lines357\" width=\"1604\" height=\"2092\" class=\"aligncenter size-full wp-image-761\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_lines357.png 1604w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_lines357-230x300.png 230w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_lines357-768x1002.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_lines357-785x1024.png 785w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_lines357-1200x1565.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>The blue lines are the boundaries to the regions of interest. Inside each region, all the points have the same number of valid cuts through them. For example, in the triangle case:<\/p>\n<ul>\n<li>the points inside the blue shape belong to three distinct cuts.<\/li>\n<li>the points on the boundary of the blue shape belong to two distinct cuts.<\/li>\n<li>the points outside the blue shape each belong to precisely one cut.<\/li>\n<\/ul>\n<p>In the figure below, I labeled the case $n=5$ with the number of cuts for each portion.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_labeled5.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_labeled5.png\" alt=\"laser_labeled5\" width=\"682\" height=\"644\" class=\"aligncenter size-full wp-image-763\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_labeled5.png 682w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_labeled5-300x283.png 300w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 984px) 61vw, (max-width: 1362px) 45vw, 600px\" \/><\/a><\/p>\n<h3>Calculating the area<\/h3>\n<p>The bonus question asks about the number of &#8220;high-risk&#8221; points. In our interpretation, this would be the points in the innermost blue pentagon (it&#8217;s not quite a pentagon since its sides are slightly curved). The points in the middle each have five intersecting cuts. In general, in the case of an $n$-sided polygon ($n$ must be odd, of course), the high-risk area will also be (roughly) an $n$-sided polygon located in the middle.<\/p>\n<p>We can calculate the area of this shape, but I wasn&#8217;t able to find an elegant way to do it. Roughly, my approach was as follows:<\/p>\n<ol>\n<li>Start with parametric equations $x(t)$ and $y(t)$ for each of the curves.<\/li>\n<li>Solve for the intersection points between adjacent rotated versions of the curves (these are the vertices of the inner rounded polygon).<\/li>\n<li>Convert these intersection points into an interval $t \\in [t_1,t_2]$ that allows our original parametric equations to sweep out one side of the inner rounded polygon.<\/li>\n<li>Integrate to find the area of the radial sector of the inner polygon using the cross-product formula for area:<br \/>\n\\[<br \/>\nA = \\int_{t_1}^{t_2} |x'(t) y(t) &#8211; x(t) y'(t)|\\,dt<br \/>\n\\]<\/li>\n<li>Multiply the area of the sector by $n$ to get the total area of the inner rounded polygon.<\/li>\n<li>Divide by the total area of the polygon ($n \\tan(\\theta)$) in our case to get the area ratio.<\/li>\n<\/ol>\n<p>The details aren&#8217;t particularly interesting. Thank goodness for Mathematica&#8230; The final result for the area ratio is:<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn.png\" alt=\"laser_eqn\" width=\"1858\" height=\"436\" class=\"aligncenter size-full wp-image-767\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn.png 1858w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn-300x70.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn-768x180.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn-1024x240.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn-1200x282.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/p>\n<p>Doesn&#8217;t appear to be a way to simplify this. For what it&#8217;s worth, this function goes to zero very fast, to the tune of $\\tfrac{1}{256}\\theta^6$. Here is what it looks like graphically.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn_plot.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn_plot.png\" alt=\"laser_eqn_plot\" width=\"1581\" height=\"1039\" class=\"aligncenter size-full wp-image-768\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn_plot.png 1581w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn_plot-300x197.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn_plot-768x505.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn_plot-1024x673.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_eqn_plot-1200x789.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>The area ratio for the case $n=5$ turns out to be $0.000333883\\dots$, or about $\\frac{1}{3000}$. <\/p>\n<h3>Pretty pictures<\/h3>\n<p>Congratulations for making it this far! Here is a neat visualization of the regions. I gave each cut thickness and transparency and used evenly spaced angles. The first picture has about 50 thick cuts while the second picture has about 2000 thin cuts. Click the figure to enlarge.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_shaded5ab.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_shaded5ab.png\" alt=\"laser_shaded5ab\" width=\"1474\" height=\"1366\" class=\"aligncenter size-full wp-image-770\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_shaded5ab.png 1474w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_shaded5ab-300x278.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_shaded5ab-768x712.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_shaded5ab-1024x949.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/laser_shaded5ab-1200x1112.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<\/div>\n<p>And here is a bonus <a href=\"https:\/\/www.geogebra.org\/m\/h4uy2dYv\">interactive graphic<\/a> showing the solution<\/p>\n<p><!--\n<iframe loading=\"lazy\" scrolling=\"no\" src=\"https:\/\/www.geogebra.org\/material\/iframe\/id\/F26GHQPB\/width\/1602\/height\/716\/border\/888888\/rc\/false\/ai\/false\/sdz\/true\/smb\/false\/stb\/false\/stbh\/true\/ld\/false\/sri\/true\/at\/auto\" width=\"1602px\" height=\"716px\" style=\"border:0px;\"> <\/iframe>\n--><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This Riddler puzzle is about cutting polygons in half. Here is the problem: The archvillain Laser Larry threatens to imminently zap Riddler Headquarters (which, seen from above, is shaped like a regular pentagon with no courtyard or other funny business). He plans to do it with a high-powered, vertical planar ray that will slice the &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/cutting-polygons-in-half\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Cutting polygons in half&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[11,10,4,2,14],"class_list":["post-745","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-conic-sections","tag-geometry","tag-integration","tag-riddler","tag-symmetry"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/745","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=745"}],"version-history":[{"count":30,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/745\/revisions"}],"predecessor-version":[{"id":827,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/745\/revisions\/827"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=745"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=745"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=745"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}