45

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!”)

Glorfindel
  • 2,743
James Propp
  • 19,363
  • May I ask: What does it mean to "extend" a line arrangement? – Joseph O'Rourke Jan 20 '14 at 19:47
  • How generic is the original/new arrangement? Do you admit multiple points? Parallel lines? – Alex Degtyarev Jan 20 '14 at 19:52
  • I find it strange that this post has received no answers and so few comments. I wonder if the whole bounty-system is distorting the priorities of the MathOverflow community, by causing MathOverflow contributors to withhold information about solved problems (or to hold off on tackling unsolved problems) until they can get a bounty for their contribution. – James Propp Jan 22 '14 at 14:15
  • Well, now there's a bounty as extra incentive. – James Propp Jan 22 '14 at 20:53
  • @JamesPropp: Do you have a counterexample for the analogous statement (involving simplices, of course) in higher dimensions? – Sam Hopkins Jan 22 '14 at 20:54
  • 1
    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 – Gerhard Paseman Jan 22 '14 at 21:01
  • 1
    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. – Adam P. Goucher Jan 22 '14 at 21:14
  • Re Sam Hopkins' first question, I suspect that the problem becomes easier (and has a negative answer) in higher dimensions, but I have no counterexamples to propose. – James Propp Jan 22 '14 at 21:56
  • Re Adam Goucher's suggestion, I find the phrase "all lines that intersect the square pass through a single point" obscure. Adam, can you clarify this for me? – James Propp Jan 22 '14 at 21:58
  • Re Gerhard Paseman's comment, I think I've learned something from this experience about modifying questions in MathOverflow. It's not enough to revise the wording of a question in response to people's queries; it's important to make it clear to everyone that one has done so! I'll try to remember to do this in the future. – James Propp Jan 22 '14 at 22:00
  • I've revised the question to include reference to an earlier, similar problem, though I doubt that this will be of much use to anyone, except as an indication that the problem is subtler than it appears at first. (Though I'm hoping that both problems eventually turn out to be simple after all, when approached in the right way.) – James Propp Jan 23 '14 at 02:59
  • @AdamP.Goucher I am confused. If a line crosses a square at two adjacent sides, this leaves a pentagon behind. I can also get a pentagon by having two lines cross inside a square, and both exit on parallel sides. – David E Speyer Jan 23 '14 at 15:11
  • 4
    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. – Ilya Bogdanov Jan 23 '14 at 15:16
  • I like Ilya Bogdanov's observation, but I don't follow his proof. Why couldn't there be a five-sided face whose sides go "old", "new", "old", "new", "new"? Or a six-sided face whose sides go "old", "new", "old", "new", "old", "new"? Clearly I'm missing something. Also, in the case where a line is both "old" AND "new" (if say $A$ is one of the original intersection points), should we interpret "old" as "non-new" in Ilya's argument? – James Propp Jan 23 '14 at 20:54
  • 1
    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$. – David E Speyer Jan 24 '14 at 05:14
  • @James, regarding bountyhunting: I think you might have received low attention due to the appended tags that are not followed by many. Offering a bounty certainly draws more attention, as there are only a few questions with a bounty. – domotorp Jan 24 '14 at 22:05
  • @domotorp: Are there other appropriate tags I should add? – James Propp Jan 25 '14 at 00:21
  • I have modified the question again, this time to suggest a related question whose solution would win the bounty if the original question proves to be too hard. – James Propp Jan 25 '14 at 04:41
  • @James: I would add combinatorial-geometry and/or discrete-geometry. – domotorp Jan 25 '14 at 07:41
  • 2
    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). – Ilya Bogdanov Jan 25 '14 at 17:37
  • 10
    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. – David Eppstein Jan 25 '14 at 18:08
  • If anyone can show that a generic triple of lines in the projective plane does not belong to any simplicial arrangement (which ought to be true, given what David Eppstein tells us), I would be inclined to award the bounty to that person. – James Propp Jan 29 '14 at 17:48
  • Isn't it the case that a generic 3-line arrangement can be extended to a simplicial arrangement by adding at each intersection of two lines the parallel to the third line? – Yoav Kallus Jan 29 '14 at 20:53
  • 1
    Leaving aside the fact that Yoav is thinking of affine space rather than projective space, the truth is even more embarrassing than his comment would suggest: if I'm thinking clearly today (as opposed to yesterday), any generic 3-line arrangement in projective space IS a triangulation! So I retract my proposal. To replace it by a more credible proposal, I'd have to acquaint myself with the prior literature that David Eppstein is implicitly citing. – James Propp Jan 30 '14 at 23:16
  • 1
    Another partial solution: Put a vertical line through every intersection. Then every bounded region is either a triangle or a trapezoid, because all vertices must lie on those vertical lines. – William Hoza Feb 27 '16 at 23:22
  • 1
    @LSpice : I had no idea that had happened. The point was a MathJax usage correction. – Michael Hardy Sep 22 '21 at 22:07
  • 1
    There are more simplicial pseudoline arrangements known than simplicial line arrangements; see Berman's "Symmetric Simplicial Pseudoline Arrangements", https://www.combinatorics.org/ojs/index.php/eljc/article/view/737 — but that doesn't make the problem trivial, or even easier, for that variation. – David Eppstein Sep 23 '21 at 07:31
  • @JamesPropp : would you be ok with a negative answer in the projective plane (it would still be weaker than the weaker condition) I think it should not be difficult to show that if we start from 4 projective lines in general position and we add one more line that can't be constructed (with the ruler) from the first 4 lines, then it won't be possible to augment in a simplicial arrangement. Maybe it is not strong enought to be in an answer eventhought I thing the general and wealker case can be deduced from the argument that I think woukd work in the more simple case of the projective plane – jcdornano Jul 28 '22 at 15:55
  • The weaker condition (unbounded are 2 or 3 side) is stronger than the condition in the projective plane because if two unbounded component have both 3 sides, and correspound to a unique component in the projective plane, then this projective component will have 4 sides – jcdornano Jul 28 '22 at 16:01
  • the dual version of Silvester-Caley thm in a stronger version shows that a simplicial argangment has to satisfy an optimal incidency condition that cannot hold if one move some lines in a certain neigbourhood while some other will remain fixed. In another hand a set of lines construced with the condition of my first comment should not change (up to homeomorphism) if we move the lines that are constructed thanks to the 5th line according to any choice of this 5th line in a fine neigbourhood, while a set of line including the first four one will remain fixed. (it's the heuristic argmt) – jcdornano Jul 28 '22 at 16:21

0 Answers0