Polygons uniquely inducing arrangements

2012-02-10T02:47:50Z

A beautiful, relatively recent result is that,

Every simple arrangement $\cal{A}$ of $n$ lines in the plane is induced by a simple $n$-gon $P$.

In a simple arrangement, every pair of lines intersect in a point, and no three lines intersect in a common point. A polygon $P$ induces $\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:

This is proved in the paper, "On Inducing Polygons and Related Problems." Eyal Ackerman, Rom Pinchasi, Ludmila Scharf, Marc Scherfenberg. Algorithms-ESA 2009. Lecture Notes in Computer Science, Volume 5757, 2009, pp, 47-58. (PDF link )

Two natural question occur to me, neither of which is addressed in the paper:

Q1. Which arrangements $\cal{A}$, $n>3$, have a unique inducing polygon?

Q2. 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?

It could be the answers are relatively easy: none and no respectively...? If anyone sees quick arguments, I'd appreciate hearing them. Thanks!

Addendum. 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.

Answer by Gjergji Zaimi for Polygons uniquely inducing arrangements

2012-04-24T01:49:14Z

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.

Polygons uniquely inducing arrangements - MathOverflow

Polygons uniquely inducing arrangements

Answer by Gjergji Zaimi for Polygons uniquely inducing arrangements