45
$\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 Link .

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.

(Historical aside: Many years ago I proposed the original version of this problem to John Conway. He said “Let me think about that,” and as the curiosity-bug bit into his brain, he began to draw pictures, make observations, and formulate conjectures. But he was no fool; he could see that I was deliberately trying to entice him into working on the problem, and he was too proud to want to be seen as one who is so easily seduced. He shuddered as if shaking off an unpleasant memory and said “You know, I don’t have to work on just ANY damned problem!”)

Improve this question
$\endgroup$
30
  • 1
    $\begingroup$ I have delayed in responding because I found the question incomplete. In particular, I wanted Joseph's question to be acknowledged. Now that I notice the acknowledgment, I am inclined to believe the answer is no, as one may set up a sequence of "problem quadrilaterals", where simple attempts to triangulate them produce more "problem quads". Further, if there is a delay of about a day in responding to comments, you might expect twice that in responding to responses. Personally, I disagree about the "bounty bias". Gerhard "Does Like Thinking For Rewards" Paseman, 2014.01.22 $\endgroup$
    – Gerhard Paseman
    Commented Jan 22, 2014 at 21:01
  • 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
    Commented Jan 22, 2014 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
    Commented Jan 23, 2014 at 15:16
  • 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
    Commented Jan 25, 2014 at 17:37
  • 10
    $\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
    Commented Jan 25, 2014 at 18:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.