MATHEMATICS
Covering points once changes the geometry
A SWAT 2026 paper separates hard point-covering problems from sparse tractable cases, while exact-cover results show why disjointness changes the question.
Research checked
Newest cited publication
Planar triangulations illustrate how connecting the same point set can produce different geometric decompositions; the article studies disjoint covering shapes.
David Eppstein / Wikimedia Commons. Wikimedia-generated PNG rendering of the SVG; no editorial changes. · Image source · Public domain (released by the creator)
A collection of circles can hide two very different questions. Must every marked point belong to exactly one disk, or must the disks themselves have no overlap anywhere? Robert D. Barish and Tetsuo Shibuya’s paper, published in the SWAT 2026 proceedings on June 8, studies geometric covering partitions, their disjoint versions, and the computational difficulty of finding or counting them. Its results combine conditional lower bounds for exact algorithms with tractable cases under explicit sparsity assumptions. Nearby work on exact unit-disk coverings provides a useful warning: removing double coverage at the marked points is weaker than forbidding overlapping regions. The distinction matters before any algorithm or existence theorem can be interpreted.
Exactly once is not disjoint everywhere
Take two unit disks with centres (0,0) and (1,0). Mark only the points (−0.9,0) and (1.9,0). The first point lies in the first disk alone, and the second lies in the second disk alone. Each observation is covered exactly once, even though the two disks overlap in a large lens. Adding the marked point (0.5,0) would expose the double coverage. This little example separates a condition on finitely many observations from a condition on every point of the plane.
The SWAT paper defines coverage-induced partitions of the input points and separately requires pairwise disjoint shapes in its stronger variant. Its disjointness condition excludes shared boundary points as well. That detail distinguishes it from interior-disjoint packings, where tangency can be allowed. A solver that treats touching disks as disjoint may answer a related problem correctly while violating the actual specification. Stating whether objects are open or closed and whether contact is allowed is part of defining the problem, not merely plotting style.
Seventeen points and a very different upper limit
Chun, Kipp and Roch’s On exact covering with unit disks proves that any set of seventeen planar points can be covered exactly once by unit disks. The same paper constructs a set of 657 points for which no exact cover exists. The published version is dated March 26, 2025, in the TU Berlin repository, while the original preprint appeared in January 2024. These numbers bracket an existence question; they are not a statement that 658 disks are necessary or that a particular algorithm becomes slow at eighteen points.
A related earlier paper, Packing-constrained point coverings by Veit Elser, studies configurations that cannot be covered by a packing of unit disks. It provides background for why a family of coverings can be easy to imagine but difficult to arrange consistently. Exact covering and disjoint covering should therefore keep their own bounds and hypotheses. In particular, the seventeen-point guarantee cannot be moved into the stronger disjoint problem simply because both are described informally as covering every point once.
An answer and a count encode different information
A decision problem asks whether an admissible arrangement exists, given the points and the allowed number of shapes. An optimization problem asks for the smallest possible number. A counting problem asks how many distinct coverage-induced partitions are possible. The last wording is deliberate: continuously moving a disk without changing which observations it covers can produce infinitely many geometric placements, yet only one partition. The counted objects must therefore be specified as combinatorial assignments rather than raw coordinates.
For four labelled points, the partition that groups the first two together and leaves the others as singletons differs from the partition grouping the last two. However, relabelling three physical disks while keeping their covered groups unchanged need not produce a new set partition. These bookkeeping choices can change a counting problem by large factors. The 2026 paper uses reductions from logical satisfiability problems to establish hardness for its precise finite objects; an implementation comparing its output with those results needs the same equivalence relation.
Read the square-root exponent carefully
For translatable unit disks, fixed-area axis-aligned squares, and translatable and rotatable fixed-area equilateral triangles, the paper rules out algorithms running in time 2 raised to o(√n), where n is the number of input points. The assumption is the Exponential Time Hypothesis, a conjecture concerning the computational difficulty of satisfiability. The result applies with and without its disjointness constraint. It should not be reported as an unconditional theorem that every program always takes exponential time.
Worst-case lower bounds allow easy instances, specialized algorithms, useful approximations and effective heuristics. They also depend on the chosen input parameter. A routine exponential in a description length can behave very differently from one exponential in the number of points. Geometry introduces further choices about coordinate representation and exact arithmetic. The exact square-root exponent matters: a running time of 2 raised to Θ(√n) remains compatible with this lower bound and is subexponential in n. The theorem does not exclude every subexponential algorithm in n. It says nothing about how long a particular small drawing will take.
A sparsity promise has a geometric scale
The positive results impose conditions on small subsets of points. In one regime, every three points must have a minimum bounding disk of radius greater than one; in another, every five must require radius at least two. The shapes considered there fit inside a disk of radius one half and have a semialgebraic description. Such a description uses finitely many polynomial inequalities, so the boundary belongs to an explicitly controlled mathematical input language.
Notice that the units in the promise matter. Multiplying all point coordinates by a thousand without scaling the allowed shape changes the problem. The radius-one-half condition and the subset-radius thresholds work together to limit local interactions. A vague statement that points are far apart would lose the quantitative content. Under its specified promises, the paper gives fixed-parameter tractability in the size of the shape description, including cases where the shape is part of the input. It does not claim that arbitrary dense unit-disk instances suddenly become easy.
Check the sparsity promise on an actual triangle
For an equilateral triangle of side s, the smallest enclosing disk has radius s divided by the square root of three. Consequently, an equilateral triple satisfies the paper’s radius-greater-than-one promise precisely when s exceeds the square root of three in the normalized units. At equality it fails the strict condition. The same drawing made slightly larger or smaller can therefore cross a theorem’s applicability boundary even though its combinatorial layout has not changed.
Checking pairwise separation alone is not the same test. Three points arranged almost on a line can have a minimum enclosing disk controlled by their most distant pair, whereas an acute triangle can require a circle supported by all three vertices. Software verifying a minimum-bounding-disk promise must handle both cases and the strictness of the comparison. With measured coordinates, uncertainty close to equality would also require care before claiming a formal promise. This is a concrete reason the positive algorithmic results state geometric conditions on subsets rather than relying on a visual impression that the point cloud is sparse.
A mathematical model should expose interference
A disk can model a nominal service region, while marked points model locations requiring service. But the distinction developed here shows what must be decided in an application. If interference matters only at known receivers, exact coverage may be the intended condition. If overlap is forbidden throughout a geographic region, pairwise disjointness is stronger and potentially wasteful. Real signals also have irregular reach and interference that does not stop sharply at a circle, so the model is a mathematical abstraction rather than a validated radio-planning system.
The research offers a useful way to think about exact geometric algorithms. First specify the objects and boundary rules. Then separate existence, optimization and counting. Finally identify a quantitative promise that removes difficult interactions and verify it on the input. The 2026 result supplies both obstruction and opportunity within that sequence. Its lesson is not that covering problems are hopeless; it is that the phrase cover these points suppresses choices that can change both the theorem and the computation.
Sources & further reading
Primary papers, project documentation, and research releases used in this article. Publication dates below refer to the sources themselves.
- Arranging Pairwise Disjoint Shapes to Partition Point SetsSchloss Dagstuhl – Leibniz-Zentrum für InformatikPublished Checked
- On exact covering with unit disksTechnische Universität Berlin / ElsevierPublished Checked
- Packing-constrained point coveringsarXivPublished Checked
FOLLOW THE QUESTION
Explore mathematics