Polygons uniquely inducing arrangements - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:27:34Z http://mathoverflow.net/feeds/question/88066 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88066/polygons-uniquely-inducing-arrangements Polygons uniquely inducing arrangements Joseph O'Rourke 2012-02-10T02:47:50Z 2012-04-24T01:49:14Z <p>A beautiful, relatively recent result is that,</p> <blockquote> <p>Every simple arrangement $\cal{A}$ of $n$ lines in the plane is induced by a simple $n$-gon $P$.</p> </blockquote> <p>In a <em>simple arrangement</em>, every pair of lines intersect in a point, and no three lines intersect in a common point. A polygon $P$ <em>induces</em> $\cal{A}$ if $\cal{A}$ is obtained by extending its $n$ edges to lines. Thus $P$ "visits" each line of $\cal{A}$ exactly once; it is a Hamiltonian-like cycle: <br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/InducedArrangment.jpg" alt="Induced Arrangement" /> <br /> This is proved in the paper, "On Inducing Polygons and Related Problems." Eyal Ackerman, Rom Pinchasi, Ludmila Scharf, Marc Scherfenberg. <a href="http://rd.springer.com/chapter/10.1007/978-3-642-04128-0_5" rel="nofollow"> <em>Algorithms-ESA 2009</em>. Lecture Notes in Computer Science, Volume 5757, 2009, pp, 47-58</a>. <a href="http://sci.haifa.ac.il/~ackerman/publications/polygonESA.pdf" rel="nofollow">(PDF link )</a></p> <p>Two natural question occur to me, neither of which is addressed in the paper:</p> <blockquote> <p><b>Q1</b>. Which arrangements $\cal{A}$, $n>3$, have a <em>unique</em> inducing polygon?</p> <p><b>Q2</b>. Does the theorem extend to $\mathbb{R}^3$, or higher dimensions? I.e., does every simple arrangement of $n$ planes have an inducing simple polyhedron of $n$ faces?</p> </blockquote> <p>It could be the answers are relatively easy: <em>none</em> and <em>no</em> respectively...? If anyone sees quick arguments, I'd appreciate hearing them. Thanks!</p> <p><b>Addendum</b>. Here is an attempt to illustrate Gjergji Zaimi's idea, as I interpret it. The hexagon induces the arrangement of lines in the horizontal plane, and the polyhedron "attached" to the hexagon would be the intersection of the two tetrahedra. <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/ArrPlanes.jpg" alt="Arrangement of Planes"></p> http://mathoverflow.net/questions/88066/polygons-uniquely-inducing-arrangements/94991#94991 Answer by Gjergji Zaimi for Polygons uniquely inducing arrangements Gjergji Zaimi 2012-04-24T01:49:14Z 2012-04-24T01:49:14Z <p>Q1: The only arrangement with a unique inducing polygon is the arrangement with three lines. In fact it follows from the first proof in the paper you cite that the number of inducing polygons is $\geq \lfloor\frac{n}{2}\rfloor$. This is because one can pick a line so that every intersection lies on the same half-plane defined by this line. Then one can pick an arbitrary intersection point $P$ on this line and produce a path which visits every line once. This path will also lie on the same half-plane so their algorithm produces an inducing polygon with $P$ as a vertex. But $P$ was arbitrary. </p>