# Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel.

It is clear that by extending the edges of each simple $n$-gon in general position we would achieve a set of $n$ lines such that no pair of lines are parallel and no triple of lines intersect in a common point. Let’s call the $n$-gon as inducing $n$-gon and the set of lines as induced arrangement of $n$ lines.

It is interesting to consider the reverse, and think about finding such an inducing $n$-gon in a given arrangement of $n$ lines which induces the arrangement, and therefore each line of the arrangement should contain exactly one side of the inducing $n$-gon. It is clear that there are arrangements that cannot be induced by a simple polygon; an arrangement of lines that all intersect in one point, and an arrangement of lines that forms a $3$ \texttimes $2$ parallel grid serve as examples of such arrangements.

It has been proved that every simple arrangement of lines contains at least one inducing $n$-gon.

It is clear that an inducing $n$-gon for an simple arrangement is not unique and there are lots of inducing $n$-gons.

Is there any suggestion or idea about complexity of counting the number of inducing $n$-gons in a simple arrangement of $n$ lines?

-
I think you need the condition that the $n$-gon is convex for the property that no three lines intersect at the same place. I can think of an easy counter-example otherwise. –  AnonymousCoward Jan 7 '11 at 18:35
Note that I want to count $n$-gons in a sets of lines such that no tree lines intersect in a common point. the $n$-gon can be convex or non-convex. I don't know if I could answer you! –  user5409 Jan 7 '11 at 19:32