40
$\begingroup$

Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that {$L_1,\dots,L_m$} is triangulating away from infinity iff every $R_j$ that is bounded is triangular.

Can every finite line-arrangement be augmented (by adding more lines) to yield one that is triangulating away from infinity?

(The old and new arrangements need not be generic; they may have parallel lines and/or multiple intersections.)

Some background: A slightly different (and, in my view, less natural) question was raised by me about twenty years ago; it has never been answered either. That problem first appeared in Richard K. Guy and Richard J. Nowakowski’s American Mathematical Monthly column on open problems (see “Bite-Sized Combinatorial Geometry Problems”, AMM, Vol. 103, No. 4, Apr. 1996, p. 342 and “Monthly Unsolved Problems”, AMM, Vol. 104, No. 10, Dec. 1997, pp. 969-970). Stan Wagon invited the readers of his on-line column to completely solve a one-parameter class of problems of this kind in which three lines symmetrically divide an equilateral triangle; see http://mathforum.org/wagon/spring96/p812.html .

A related problem that might be simpler to solve in the negative is a version in which we not only require that all bounded components have 3 sides but also require that all unbounded components have 2 or 3 sides. If nobody can solve my original problem affirmatively or negatively, a negative solution to this problem would deserve the bounty.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Observe that it is possible to extend an arrangement to one that is `quadrilateralating away from infinity' by superimposing a sufficiently large square mesh (two perpendicular families of parallel lines), where the squares are sufficiently small that all lines that intersect the square pass through a single point. $\endgroup$ – Adam P. Goucher Jan 22 '14 at 21:14
  • 4
    $\begingroup$ It is easy to "quadrilaterate away" just by choosing a point $A$ and drawing all lines connecting $A$ with all intersection points of the original lines. Each resulting region will have at most four sides because it cannot contain two consecutive sides on "old" lines. $\endgroup$ – Ilya Bogdanov Jan 23 '14 at 15:16
  • 1
    $\begingroup$ Don't take $A$ to be on one of the old lines. Any 3 new lines all pass through $A$, so 3 new lines cannot all be sides of a convex region. Thus, any region $D$ lies in a wedge between two consecutive new lines, call them $L$ and $L'$. Then $\partial D \setminus (\partial D \cap (L \cup L'))$ consists of two paths, call them $p$ and $q$. (Or, if $A$ is at a corner of $D$, one path.) If $p$ contains more than one old line, then it has an internal vertex $v$. But there would be a new line through $v$, contradicting that $L$ and $L'$ are consecutive. So $p$ is a single segment, and likewise $q$. $\endgroup$ – David E Speyer Jan 24 '14 at 5:14
  • 2
    $\begingroup$ It would be also interesting to find whether the answer to the question is affirmative if we replace lines by pseudolines (that is --- unbounded curves or olylines satisfying the property that every two of them intersect at exactly one point; here we omit parallel lines). $\endgroup$ – Ilya Bogdanov Jan 25 '14 at 17:37
  • 8
    $\begingroup$ In case you're unaware (since I didn't see any mention of it in the question): these things are more commonly studied in the projective plane, where there is no distinction between bounded and unbounded. An arrangement of lines or pseudolines in the projective plane for which all faces are three-sided is called a simplicial arrangement. There are only a few infinite families of them known, so certainly it is not known that everything else can be augmented to become simplicial. $\endgroup$ – David Eppstein Jan 25 '14 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.