# Polygons uniquely inducing arrangements

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.

-
For Q2, if I'm not mistaken, you can take the line arrangement induced on one of the planes, pick a simple inducing polygon there and then find the smallest polyhedron attached to this polygon. –  Gjergji Zaimi Feb 10 '12 at 2:58
The proof of the paper by Ackerman, Pinchasi, Scharf and Scherfenberg shows also that there exists a homologically non-trivial Hamiltonian cycle for simple arrangements of the projective plane. –  Roland Bacher Feb 10 '12 at 12:45
@Gjergji: Very nice idea! Can you expand on "smallest"? It seems if your idea works, it settles the question in any dimension. –  Joseph O'Rourke Feb 10 '12 at 13:54
You had a picture in your gallery of something I call a "Klingon triangle"; it was by Jeff Erickson KHi Jeff!)Gerhard and was a counterexample to some result about one polygon that could not be transformed to another using certain motions that would create interesting looking prisms. That might induce a unique arrangement, but the pentagon does not because you have four lines that can "flex" around a middle vertex. Gerhard "Ask Me About System Design" Paseman, 2012.02.10 –  Gerhard Paseman Feb 10 '12 at 15:05
There are no simple polyhedrons with exactly 5 sides, so any simple arrangement of 5 planes will be a counterexample for Q2. –  Zsbán Ambrus May 4 '12 at 13:42
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.