Counting polygons in arrangements For an arrangement of lines $\cal{A}$ in the plane, an
inducing polygon $P$ is a simple polygon satisfying:
(a) every edge $e$ of $P$ lies on some line $\ell$ of $\cal{A}$, and
(b) every line $\ell \in \cal{A}$ is collinear with an edge $e$ of $P$.
If $P$ has $k$ edges and $\cal{A}$ has $n$ lines, $k \ge n$.
Note that several edges of $P$ might lie on the same line of $\cal{A}$.
It is known that if the lines in $\cal{A}$ are in general position
in the sense that no two lines are parallel and no three lines meet in a point,
then $\cal{A}$ has an inducing polygon.1
My questions concern counting the inducing polygons.

          



Q. Over all arrangements $\cal{A}$ of $n$ lines in general position,
what are upper and lower bounds on the number of inducing polygons
for $\cal{A}$, and which arrangements achieve those bounds?

To clarify (thanks MaxAlekseyev): Let $\cal{A}$ be a specific arrangement of $n$ lines
in general position. $\cal{A}$ supports a certain number of incongruent
inducing polygons. What are max and min of this number, over all arrangements of $n$ lines?
Other possibly easier questions suggest themselves, e.g.:
Does any arrangement ever have more than one convex inducing polygon?
My original aim was to find a minimum area inducing polygon,
which is likely difficult.


1Scharf, Ludmila, and Marc Scherfenberg.
"Inducing polygons of line arrangements."
In International Symposium on Algorithms and Computation,
pp. 507-519. Springer, Berlin, Heidelberg, 2008.
Springer link.

 A: Going to the geometric dual,

*

*lines map to points with polar coordinates $(\varphi,\,r)$ where $\varphi$ is the angle of the normal, pointing away from the origin, with the positive $x$-axis and $r$ the distance of the origin to the line

*pairs of intersecting lines in the euclidean plane map to line-segments connecting the respective dual points.

*point-segment arrangemnts in the dual plane can be interpreted as planar embeddings of graphs and simple arrangements of lines yield a complete graph.

That simple arrangement of lines yield a complete graph implies that they can always be represented by a single polygon: any Hamilton cycle through the points in the dual plane will do.
The other questions seem to be answered by results about cell complexes, some of which arein the cited wikipedia article like e.g."Although a single cell in an arrangement may be bounded by all n lines, it is not possible in general for m different cells to all be bounded by n lines. Rather, the total complexity of m cells is at most $Θ(m^{2/3}n^{2/3} + n)$,[11] almost the same bound as occurs in the Szemerédi–Trotter theorem on point-line incidences in the plane"

$ILP$ formulation
If a one-to-one correspondence between lines and polygon sides is desired, then a integer linear programming formulation may yield solutions that can be subjected to desirable optimization criteria:
the binary variables correspond to the edges created by splitting the lines at the intersection points, the constraints being that the variables of collinear edges sum to $1$ and that in every intersection of two lines the sums of the variables corresponding to their adjacent edges are equal, i.e.
if $l_{1i},l_{i1},l_{2,i},l_{i2}$ are the binary variable corresponding to the edges of lines $L_1$ and $L_2$ that intersect in point $(x_i,y_i)$, then $l_{1i}+l_{i1}=l_{2,i}+l_{i2}$ must be satisfied.
Imposing subtour elimination constraints may answer the existence of a single polygon with bijection between its edges and the lines.
