CS Paper Radar

Non-simple Arrangements of Lines and Pseudolines with Many Triangles

Roman Parpalak, Denis Utkin

cs.CG math.CO ·submitted 2026-11-02 13:13 UTC · v1
code/data

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.

Comment
72 pages, 19 figures, 8 tables. Code, enumeration outputs and certificates: https://github.com/parpalak/nonsimple-arrangements

Closest papers

Nearest neighbours by meaning across the whole index.

$k$-arrangements of pseudolines and pseudocircles

cs.CG math.CO ·2026-09-30 ·Jan Kynčl, Carolina Medina, Gelasio Salazar
theory similarity 0.69
Abstract · 19 pages, 10 figures

A $k$-arrangement of pseudolines is a set of bi-infinite curves in the plane such that any two of them intersect each other in exactly $k$ points, at which they cross, and it is simple if no three curves meet at a common point. Cyclic arrangements are the only simple $1$-arrangements of pseudolines that are unavoidable, in the Ramsey spirit: for each fixed $m\ge 1$, every sufficiently large simple $1$-arrangement of pseudolines has a cyclic subarrangement of size $m$. We show that, for every $m\ge 3$, the number of unavoidable simple $k$-arrangements of pseudolines of size $m$ grows exponentially with $k$, independently of $m$. For even $k$, we prove an analogous result for $k$-arrangements of pseudocircles.

0.27

Triangle Covers of Polygons: Approximation Algorithms and Complexity

cs.CG ·2026-10-16 ·Linda Kleist, Lena Scherzer
similarity 0.59
Abstract · 37 pages, 32 figures, GeoGebra file

We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity of partitioning a simple polygon into a minimum number of triangles is open. Our main result refutes a 40 year old conjecture by Asano, Asano, and Pinter stating that the triangle vertices of a minimum partition lie on intersection points of special lines, which are iteratively generated by the polygon vertices and the intersection points. In particular, we show that there exist polygons where all minimum triangle partitions need Steiner points with irrational coordinates. This indicates that the problem might be more complex than previously expected. Complementarily, we provide a simple constant factor approximation to compute a minimum triangle partition of a given polygon (possibly with holes). In the context of coverings, we devise the first constant factor approximation for computing a minimum triangle cover of a simple polygon. For general polygons, an $O(\log n)$-approximation follows by close inspection of previous work.

0.27

Almost Linear Universal Point Sets for Planar Graphs

cs.CG math.CO ·2026-09-10 ·Taylor Gordon
theorycode/data similarity 0.59
Abstract · 12 pages, 2 figures. Lean formalization of the earlier construction: https://github.com/taylorgordon20/math/tree/main/213-superpatterns

A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

0.37

Bichromatic Line-Centers for Point Pairs

cs.CG ·2026-09-20 ·Jaegun Lee, Youjung Bae, Taehoon Ahn, Sang Won Bae, Hee-Kap Ahn
similarity 0.58
Abstract

We study the \emph{bichromatic line-center problem} for $n$ pairs of points in the plane. A feasible solution assigns one point from each pair to the red set $R$ and the other to the blue set $B$. The goal is to minimize $\max\{w^\circ(R),\,w^\circ(B)\}$, where $w^\circ(X)$ denotes the minimum width of a strip enclosing $X$; the midlines of the corresponding optimal strips define the line-centers of $R$ and $B$. We consider several variants induced by orientational constraints on line-centers and provide efficient algorithms for each. For one line-center, which consists of computing a minimum-width strip that contains at least one point from each pair, we give an $O(n^2)$-time algorithm. For two line-centers, we obtain an $O(n)$-time algorithm when both are horizontal, and $Θ(n\log n)$-time algorithms when the two centers are parallel or when both orientations are prescribed. When exactly one orientation is prescribed, we give an $O(n^2)$-time algorithm. Finally, for the unrestricted case, we present an $O(n^3\log n)$-time algorithm.

0.20

On Guarding Line Arrangements

cs.CG math.CO ·2026-11-01 ·Valentin Brimkov
similarity 0.57
Abstract · 21 pages, no figures

We study the problem of guarding a set of straight lines in the plane by selecting a minimum-cardinality set of points such that every line contains at least one selected point. This problem is known to be strongly NP-hard \cite{megiddo}. We investigate approximation algorithms for the problem and analyze their performance guarantees under various structural assumptions on the underlying line arrangement. In particular, we present approximation schemes based on set-cover techniques, relaxation methods, and properties of maximal lines. We establish constant-factor bounds on the approximation ratio for several classes of arrangements and derive relationships between the guarding number and the incidence parameters of the arrangement. Connections with Dirac-type incidence results are also explored.

0.28

Some results on Archdeacon's conjecture for rotation systems

cs.CG math.CO ·2026-09-10 ·Arahat Chikkatur, Ji Zeng
theory similarity 0.57
Abstract

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

0.39

Optimal Configurations for Mordell's Problem

cs.SC math.COmath.OC ·2026-11-02 ·Xiang Ji, Tiancheng Xu, Wensheng Yu
theoryunusual similarity 0.57
Abstract

Mordell's problem asks for the largest product of squared pairwise distances among $n$ points in the complex plane with a prescribed sum of squared distances from the origin. When this sum equals $n$, the maximum for $2\le n\le5$ is known to be $n^n$, attained precisely by the $n$th roots of unity up to rotation and relabeling. For $n\ge6$, Chalk showed that a regular polygon together with its center gives a larger product than the regular $n$-gon. We prove that for $6\le n\le9$ the maximum is $(n-1)^{n-1}r_n^{n(n-1)}$, where $r_n=\sqrt{n/(n-1)}$. Up to the same symmetries, the unique maximizer consists of the origin and the vertices of a regular $(n-1)$-gon of radius $r_n$. For six points, algebraic elimination reduces the proof to an exact comparison of stationary values. For seven points, we compare all twelve classes in a published classification of equilibria. For eight and nine points, rigorous interval arithmetic establishes an inequality for every admissible pair. Summing over pairs gives the sharp global bound, and the equality conditions determine the configuration. An explicit ten-point comparison and a known instability result together exclude Chalk's configuration for every $n\ge10$. For each $n$ from two through eight, Mordell's problem and the minimum-diameter problem studied by Bateman and Erdős have a common optimal configuration.

0.29

An upper bound on the number of edges of a Gomory corner polyhedron

cs.CG math.COcs.DMmath.OC ·2026-11-12 ·A. Yu. Chirkov, S. I. Veselov, D. V. Gribanov, D. S. Malyshev, N. Yu. Zolotykh
theory similarity 0.57
Abstract

We establish the first nontrivial upper bound on the number of edges of a Gomory corner polyhedron, resolving a long-standing open question. For an $n$-dimensional corner polyhedron associated with an integer lattice of determinant $δ$, the number of edges is at most $$ O\left(n6^n \cdot \bigl(1+\log_2(2δ)\bigr)^{2n-3}\right). $$ This improves the standard bound obtained by counting pairs of vertices, reducing the logarithmic exponent from $(2n-2)$ to $(2n-3)$.

0.28