## Polygons uniquely inducing arrangements

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

2
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 2012 at 2:58

1
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 2012 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 2012 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 2012 at 15:05

1
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 2012 at 13:42
show 2 more comments

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9120215773582458, "perplexity_flag": "middle"}