11
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Commented Feb 10, 2012 at 2:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Roland Bacher
    Commented Feb 10, 2012 at 12:45
  • $\begingroup$ @Gjergji: Very nice idea! Can you expand on "smallest"? It seems if your idea works, it settles the question in any dimension. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 10, 2012 at 13:54
  • 2
    $\begingroup$ There are no simple polyhedrons with exactly 5 sides, so any simple arrangement of 5 planes will be a counterexample for Q2. $\endgroup$
    – Zsbán Ambrus
    Commented May 4, 2012 at 13:42
  • 1
    $\begingroup$ Might there be a unique smallest or unique convex inducing polygon? $\endgroup$
    – user44143
    Commented May 21, 2017 at 1:56

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .