1
$\begingroup$

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?

  • 0
    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!2011-01-07

0 Answers 0