Arrangements of lines and pseudolines with maximum triangles exceed known bounds
Non-simple Arrangements of Lines and Pseudolines with Many Triangles
Computational Geometry
Summary
Arrangements of lines or similar curves can form many triangular regions where they intersect. Previous limits suggested how many triangles are possible when intersections are simple, but the authors found examples with special multiple intersections that create even more triangles. They identified precise numbers and patterns for these arrangements, including some that cannot be made with only straight lines. Their work leads to a new guess about the absolute maximum number of triangles possible in such arrangements.
What this means in practice
- •For computational geometers: Construct and analyze geometric arrangements with the maximal number of triangles including non-simple intersections.
- •For graph visualization developers: Use insights on line and pseudoline arrangements to design better visualization layouts with optimized triangular regions.
Authors
Roman Parpalak, Denis Utkin
Abstract
We study affine arrangements of an even number $n$ of lines and pseudolines with many triangles. For simple ones, Blanc's bound limits the number of triangular faces to $\lfloor n(n-5/2)/3\rfloor$. Adapting the Bartholdi-Blanc-Loisel doubling to the even case, we construct an infinite series of arrangements of $n=6\cdot2^t+2$ ($8,14,26,50,\ldots$) straight lines with two triple points and $(n(n-5/2)+1)/3$ triangles, one more than the simple bound allows. We obtain exhaustive enumerations of triangle-maximal pseudoline arrangements, simple or not, for even $n\le12$. For $n=6,8,10,12,14$ the maximum number of triangles, for both lines and pseudolines, is $7,15,25,38,54$; for $n=8,12,14$ every optimal arrangement has multiple points. All optimal arrangements for even $n\le12$ are realizable by straight lines, except two arrangements of 10 pseudolines, which are not stretchable. For the odd value $n=11$, no arrangement with $33$ triangles exists even with multiple points. We also obtain even arrangements by adding a line to odd ones. For $n\equiv2\pmod 6$ this again gives one triangle more than the simple bound, in pseudolines up to $n=44$ and in straight lines for $n=20$ and $n=32$. Doubling these pseudoline arrangements gives members of the series $18\cdot2^t+2$ and $30\cdot2^t+2$ with the same excess, up to $n=146$ and $n=242$, respectively; those with $n=38$ and $n=74$ are realizable by straight lines. These results lead us to conjecture that an arrangement of an even number $n$ of pseudolines has at most $\lfloor n(n-2)/3\rfloor-\lfloor n/6\rfloor$ triangles.