CS Paper Radar

On Guarding Line Arrangements

Valentin Brimkov

cs.CG math.CO ·submitted 2026-11-01 16:49 UTC · v1

Abstract

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.

Comment
21 pages, no figures

Closest papers

Nearest neighbours by meaning across the whole index.

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.61
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

Non-simple Arrangements of Lines and Pseudolines with Many Triangles

cs.CG math.CO ·2026-11-02 ·Roman Parpalak, Denis Utkin
code/data similarity 0.57
Abstract · 72 pages, 19 figures, 8 tables. Code, enumeration outputs and certificates: https://github.com/parpalak/nonsimple-arrangements

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.

0.34

Avoiding Distances

cs.CG cs.DMmath.CO ·2026-10-17 ·Adrian Dumitrescu, Zsolt Lángi
similarity 0.54
Abstract · 14 pages, two figures

Given a finite planar point set $X=\{x_1,\ldots,x_n\}$, let $a_1<a_2< \cdots < a_s$ denote the $s \leq {n \choose 2}$ different (Euclidean) distances between points in $X$. The aim is to retain as many of the points as possible such that certain imposed inter-pair distances are avoided. For example, we show that: (A) Given a set $X$ of $n$ points in the plane, an independent set of size $0.2293 n$ in the unit distance graph determined by $X$ can be found in $O(n^2)$ time. For any fixed $k \in \mathbf{N}$ there exists a constant $c_k>0$ such that for any set $X$ of $n$ points in the plane, and set $D$ of size $k$, there exists a subset $X' \subseteq X$ of size $|X'| \geq c_k |X|$ in which no pair of points is at some distance in $D$ (we say that $X'$ avoids distances in $D$). Such a set can be found efficiently. (B) (i) There is a subset of $X$ of size $n/2$ that avoids the maximum distance; this bound cannot be improved. (ii) There is a subset of $X$ of size $8n/47$ that avoids both the minimum and maximum distance; on the other hand, there exists $X$ such that at most $5n/16$ points can be retained with this property. (iii) There is a subset of $X$ of size $n/7$ whose diameter is at most half the original diameter; on the other hand, there exists $X$ such that at most $n/6$ points can be retained with this property. (C) (i) For any $\varepsilon>0$, a $(1-\varepsilon)$-approximation for \textsc{MIS} in the minimum distance graph of $n$ points in the plane can be found in $2^{O(1/\varepsilon)} n^{O(1)}$ time. (ii) Given a set $X$ of $n$ points in the plane, a maximum independent set in the graph of diameters can be computed in $O(n^2)$ time. The techniques used to handle the planar case can be extended to $\mathbf{R}^d$ for any fixed dimension $d$.

0.28

Exact algorithms for optimal discretization

cs.DS ·2026-08-25 ·László Kozma, Junqi Tan
published similarity 0.53
Abstract · To appear in IPEC 2026

The optimal discretization problem asks, given two disjoint sets of points $R$ and $B$ in the plane, for a minimal family of horizontal and vertical lines that separate the two sets, so that no cell delimited by the lines contains points from both sets. The problem arises as a pre-processing in supervised machine learning, and has received significant attention in parameterized algorithmics. Answering the question raised by Bonnet, Giannopoulos, and Lampis [IPEC 2017] and Froese [PhD thesis, 2018], it was shown by Kratsch, Masařík, Muzi, Pilipczuk, and Sorge [SODA 2021] that optimal discretization admits a fixed-parameter algorithm with running time $2^{\mathcal{O}(k^2 \log k)} \cdot n^{\mathcal{O}(1)}$, where $k$ is the solution size and $n = |R| + |B|$. In this paper we give an algorithm for optimal discretization that runs in time $\mathcal{O}(1.9602^n)$. We also study the related point separation problem that asks to separate all input points by axis-parallel lines. For this problem we obtain an algorithm with runtime $\mathcal{O}(1.8899^n)$. Our guarantees follow from structural observations about bichromatic and monochromatic point sets. To our knowledge, these are the first improvements over the trivial $2^n$ bound for both problems.

0.39

$k$-arrangements of pseudolines and pseudocircles

cs.CG math.CO ·2026-09-30 ·Jan Kynčl, Carolina Medina, Gelasio Salazar
theory similarity 0.53
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

A 4.542-approximation for the Small Cuts Cover problem via a multi-rate primal-dual algorithm

cs.DS ·2026-11-17 ·Zeev Nutov, Elazar Koren
similarity 0.52
Abstract

In the Small Cuts Cover problem we seek to cover by a min-cost edge-set the set-family of cuts of size $<k$ of a graph. Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1-15:19] showed that the classic primal-dual algorithm with reverse delete of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708-717] achieves approximation ratio $16$ for this problem. The analysis of the approximation ratio was then improved in a sequence of papers, culminating in the $5$-approximation by Simons, Bansal, and Cheriyan. A matching example of Nutov shows that this bound is tight for the classic algorithm. We improve the approximation ratio to $(3+\sqrt{37})/2<4.542$ using a multi-rate primal-dual algorithm (that applies for strongly pliable set-families) in which the dual variables of the inclusion-minimal violated sets are not raised uniformly, but with different rates. We also provide a tight example. To the best of our knowledge, this is the first example in network design where for the standard LP, an efficiently computable choice of growth rates improves on the tight guarantee of uniform growth.

0.21

Almost Linear Universal Point Sets for Planar Graphs

cs.CG math.CO ·2026-09-10 ·Taylor Gordon
theorycode/data similarity 0.52
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

Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

cs.LG ·2026-09-16 ·Yingquan, Wu, Jason Cong
theory similarity 0.51
Abstract

We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.

0.33