Sign up ×

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:
            Induced Arrangement
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.
           Arrangement of Planes

share|cite|improve this question
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

1 Answer 1

up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


