pith. sign in

arxiv: 2301.04350 · v3 · submitted 2023-01-11 · 💻 cs.CG

Maximum Centre-Disjoint Mergeable Disks

Ali Gholami Rudi This is my paper

Pith reviewed 2026-05-24 10:35 UTC · model grok-4.3

classification 💻 cs.CG
keywords NP-hardnessdisk selectioncentre-disjointmergeable disksmap labellinginteger linear programmingcollinear centerscomputational geometry
0
0 comments X

The pith

The maximum centre-disjoint mergeable disks problem is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that selecting the largest subset of disks such that no selected disk contains the center of another, and every unselected disk can merge into a selected one by radius growth, cannot be solved in polynomial time unless P equals NP. A reader cares because the model directly captures label placement on rotating maps and entity visualization on static maps, where labels must avoid overlapping centers yet expand to cover nearby points. The authors establish hardness through a reduction, supply an integer linear program that finds optimal subsets for moderate instances, and give an efficient algorithm when all disk centers lie on one line.

Core claim

The central claim is that the maximum centre-disjoint mergeable disks problem is NP-hard. The authors prove this hardness result, present an integer linear programming formulation that computes an optimal subset, and describe a polynomial-time algorithm that works when every disk center lies on a straight line.

What carries the argument

The centre-disjoint mergeable subset: a largest collection of disks whose interiors are pairwise center-disjoint and where every omitted disk has at least one selected disk whose radius can be increased to contain it without violating the center-disjoint condition.

If this is right

  • No polynomial-time exact algorithm exists for the general problem unless P=NP.
  • The integer linear program yields optimal solutions on instances of moderate size.
  • When all centers are collinear, the maximum subset can be found in polynomial time.
  • Map-labelling applications can therefore use the ILP for small maps and the line algorithm when centers align.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The collinear algorithm may extend to other low-dimensional restrictions such as centers on a circle or in a narrow strip.
  • Practical map-labelling systems will likely need approximation or heuristic methods once instance size exceeds what the ILP can handle.
  • The mergeability condition may be relaxed to allow limited radius increases, potentially changing both hardness and algorithmic results.

Load-bearing premise

Every disk outside the chosen subset can always be absorbed by increasing the radius of some nearby chosen disk while the chosen subset remains center-disjoint.

What would settle it

A polynomial-time algorithm that computes the maximum centre-disjoint mergeable subset for arbitrary disk positions in the plane.

Figures

Figures reproduced from arXiv: 2301.04350 by Ali Gholami Rudi.

Figure 1
Figure 1. Figure 1: An example rotating map with 4 labels. (a) The initi [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The distribution of schools in Munich; disks corre [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example set of disks with two proper assignments [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An example set of disks with no proper assignment. E [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A monotone rectilinear representation of a P [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Two gadgets (Parts (a) and (b)), joined at one of the [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Gadgets used in the proof of Theorem 3.6; [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: A PROPER MCMD instance obtained from the PLANAR MONOTONE 3-SAT instance of [PITH_FULL_IMAGE:figures/full_fig_p010_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The construction in the proof of Theorem 3.12. Only [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Demonstrating the symbols used in Theorem 4.4. [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
read the original abstract

Given a set of disks in the plane, the goal of the problem studied in this paper is to choose a subset of these disks such that none of its members contains the centre of any other. Each disk not in this subset must be merged with one of its nearby disks that is, increasing the latter's radius. This problem has applications in labelling rotating maps and in visualizing the distribution of entities in static maps. We prove that this problem is NP-hard. We also present an ILP formulation for this problem, and a polynomial-time algorithm for the special case in which the centres of all disks are on a line.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The paper defines the Maximum Centre-Disjoint Mergeable Disks problem: given disks in the plane, select a maximum subset S such that no disk in S contains the center of another disk, and every disk outside S can be merged into a nearby disk in S by increasing the radius of the disk in S. The authors claim to prove NP-hardness, supply an ILP formulation, and give a polynomial-time algorithm when all centers are collinear. Applications to rotating map labelling and static map visualization are noted.

Significance. If the NP-hardness result and algorithms hold under a non-trivial merge definition, the work introduces a geometrically constrained variant of independent set with direct applications in cartography. The explicit ILP and the special-case polynomial algorithm constitute concrete contributions that could be built upon.

major comments (3)
  1. [§2] §2 (problem definition): The formal condition for a disk D to be 'mergeable' into a selected disk S (via radius increase of S while preserving centre-disjointness of the selected set) is not stated with an explicit distance or radius bound. The abstract's reference to 'nearby' disks leaves open whether the merge condition is always satisfiable for any centre-disjoint S; if so, the problem reduces to maximum centre-disjoint set and the claimed NP-hardness requires an explicit reduction that encodes the bound.
  2. [§3] §3 (NP-hardness): The reduction establishing NP-hardness must be checked against the precise merge predicate; if the predicate permits unbounded radius growth, the reduction would need to force the bound via gadget geometry, yet no such detail is visible in the high-level claim.
  3. [§4] §4 (line case): The polynomial-time algorithm for collinear centers must be shown to exploit the merge condition rather than merely solving maximum centre-disjoint set on an interval graph; the running time and correctness argument should be stated explicitly with respect to the merge definition.
minor comments (1)
  1. [Abstract] The abstract states the three main results but supplies no section pointers; adding 'see §3', 'see §4', etc., would improve readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We address each major comment below.

read point-by-point responses

  1. Referee: [§2] §2 (problem definition): The formal condition for a disk D to be 'mergeable' into a selected disk S (via radius increase of S while preserving centre-disjointness of the selected set) is not stated with an explicit distance or radius bound. The abstract's reference to 'nearby' disks leaves open whether the merge condition is always satisfiable for any centre-disjoint S; if so, the problem reduces to maximum centre-disjoint set and the claimed NP-hardness requires an explicit reduction that encodes the bound.

    Authors: We agree that the merge condition should be stated with greater formality. The manuscript defines mergeability via a radius bound that depends on distances to other selected centers in order to preserve centre-disjointness; this bound is not always satisfiable for an arbitrary centre-disjoint set. We will revise §2 to include an explicit mathematical statement of the predicate. revision: yes

  2. Referee: [§3] §3 (NP-hardness): The reduction establishing NP-hardness must be checked against the precise merge predicate; if the predicate permits unbounded radius growth, the reduction would need to force the bound via gadget geometry, yet no such detail is visible in the high-level claim.

    Authors: The reduction is constructed so that gadget geometry enforces the merge bounds. We will expand the presentation in the revised §3 to make the interaction between the reduction and the merge predicate explicit. revision: yes

  3. Referee: [§4] §4 (line case): The polynomial-time algorithm for collinear centers must be shown to exploit the merge condition rather than merely solving maximum centre-disjoint set on an interval graph; the running time and correctness argument should be stated explicitly with respect to the merge definition.

    Authors: The linear-time algorithm incorporates the merge condition by tracking allowable radius extensions constrained by selected centers on the line. We will revise §4 to state the running time explicitly and to include a correctness argument written directly in terms of the merge predicate. revision: yes

Circularity Check

0 steps flagged

No circularity: standard NP-hardness and algorithmic results

full rationale

The paper states it proves NP-hardness, gives an ILP, and gives a poly-time algorithm for the collinear-centers case. These are presented as conventional complexity and algorithmic results with no self-definitional steps, no fitted parameters renamed as predictions, and no load-bearing self-citations. The problem definition (centre-disjoint subset plus mergeability of outsiders) is given directly; nothing in the abstract or described claims reduces the hardness proof or algorithm to its own inputs by construction. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no information is given on any free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5617 in / 1052 out tokens · 33575 ms · 2026-05-24T10:35:39.946195+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    A Packing Problem with Applications to Lettering of Maps

    Formann M, Wagner F. A Packing Problem with Applications to Lettering of Maps. In: Symposium on Computational Geometry (SoCG). ACM, North Conway, NH, US A, 1991 pp. 281–288. doi:10.1145/ 109648.109680

    work page arXiv 1991

  2. [2]

    Clique is hard to approximate within n1−ǫ

    H˚ astad J. Clique is hard to approximate within n1−ǫ. Acta Math. , 1999. 182(1):105–142. doi:10.1007/ BF02392825

    work page 1999

  3. [3]

    Fowler, Mike Paterson, and Steven L

    Fowler RJ, Paterson M, Tanimoto SL. Optimal Packing and C overing in the Plane are NP-Complete. Information Processing Letters, 1981. 12(3):133–137. doi:10.1016/0020-0190(81)90111-3

    work page doi:10.1016/0020-0190(81)90111-3 1981

  4. [4]

    Approximation Schemes for Coverin g and Packing Problems in Image Process- ing and VLSI

    Hochbaum DS, Maass W . Approximation Schemes for Coverin g and Packing Problems in Image Process- ing and VLSI. J. ACM, 1985. 32(1):130–136. doi:10.1145/2455.214106

    work page doi:10.1145/2455.214106 1985

  5. [5]

    Label Placement by Max imum Independent Set in Rectangles

    Agarwal PK, van Kreveld MJ, Suri S. Label Placement by Max imum Independent Set in Rectangles. Comput. Geom., 1998. 11(3–4):209–218. doi:10.1016/S0925-7721(98)00028-5

    work page doi:10.1016/s0925-7721(98)00028-5 1998

  6. [6]

    Polynomial-Time Approxi mation Schemes for Geometric Intersection Graphs

    Erlebach T, Jansen K, Seidel E. Polynomial-Time Approxi mation Schemes for Geometric Intersection Graphs. SIAM J. Comput., 2005. 34(6):1302–1323. doi:10.1137/S0097539702402676. A.G. Rudi / Maximum Centre-Disjoint Mergeable Disks 67

    work page doi:10.1137/s0097539702402676 2005

  7. [7]

    Polynomial-Time Approximation Schemes for Pac king and Piercing Fat Objects

    Chan TM. Polynomial-Time Approximation Schemes for Pac king and Piercing Fat Objects. J. Algorithms,

    work page

  8. [8]

    doi:10.1016/S0196-6774(02)00294-8

    46(2):178–189. doi:10.1016/S0196-6774(02)00294-8

    work page doi:10.1016/s0196-6774(02)00294-8

  9. [9]

    Approximation Algorithms for Maxi mum Independent Set of Pseudo-Disks

    Chan TM, Har-Peled S. Approximation Algorithms for Maxi mum Independent Set of Pseudo-Disks. Discrete & Comput. Geom. , 2012. 48(2):373–392. doi:10.1007/s00454-012-9417-5

    work page doi:10.1007/s00454-012-9417-5 2012

  10. [10]

    Dynamic Map Labeling

    Been K, Daiches E, Y ap CK. Dynamic Map Labeling. IEEE Trans. Vis. Comput. Graph., 2006. 12(5):773–

    work page 2006

  11. [11]

    doi:10.1109/TVCG.2006.136

    work page doi:10.1109/tvcg.2006.136 2006

  12. [12]

    Consistent Labeling o f Rotating Maps

    Gemsa A, N¨ ollenburg M, Rutter I. Consistent Labeling o f Rotating Maps. Comput. Geom. , 2011. 7(1):308–331. doi:10.20382/jocg.v7i1a15

    work page doi:10.20382/jocg.v7i1a15 2011

  13. [13]

    Evaluation of Labeling Strategies for Rotating Maps

    Gemsa A, N¨ ollenburg M, Rutter I. Evaluation of Labeling Strategies for Rotating Maps. ACM J. Experim. Algor ., 2016. 21(1):1.4:1–1.4:21. doi:10.1145/2851493

    work page doi:10.1145/2851493 2016

  14. [14]

    Fast Optimal Labelin gs for Rotating Maps

    Cano RG, de Souza CC, de Rezende PJ. Fast Optimal Labelin gs for Rotating Maps. In: Workshop on Algorithms and Computation (W ALCOM). Springer, Hsinchu, T aiwan, 2017 pp. 161–173. doi:10.1007/ 978-3-319-53925-6 13

    work page 2017

  15. [15]

    Polynomial Time Algorithms for Labe l Size Maximization on Rotating Maps

    Y okosuka Y , Imai K. Polynomial Time Algorithms for Labe l Size Maximization on Rotating Maps. J. Inform. Process., 2017. 25:572–579. doi:10.2197/ipsjjip.25.572

    work page doi:10.2197/ipsjjip.25.572 2017

  16. [16]

    Crushing Disks Efficientl y

    Funke S, Krumpe F, Storandt S. Crushing Disks Efficientl y. In: IWOCA. Springer, Helsinki, Finland, 2016 pp. 43–54. doi:10.1007/978-3-319-44543-4 4

    work page doi:10.1007/978-3-319-44543-4 2016

  17. [17]

    Bayesian Segmentation of Atrium Wall Using Globally-Optimal Graph Cuts on 3D Meshes

    de Berg M, Khosravi A. Optimal Binary Space Partitions i n the Plane. In: COCOON. Springer, Nha Trang, Vietnam, 2010 pp. 216–225. doi:10.1007/978-3-642- 14031-0 25

    work page doi:10.1007/978-3-642- 2010

  18. [18]

    Maximizing the Number of Visible Labels on a Rot ating Map

    Rudi AG. Maximizing the Number of Visible Labels on a Rot ating Map. Sci. Ann. Comput. Sci. , 2021. 31(2):275–287. doi:10.7561/SACS.2021.2.293

    work page doi:10.7561/sacs.2021.2.293 2021

  19. [19]

    Hardness of Detecting Abelian and Additive Square Factors in Strings

    Kaplan H, Klost K, Mulzer W , Roditty L, Seiferth P , Shari r M. Triangles and Girth in Disk Graphs and Transmission Graphs. In: European Symposium on Algorit hms (ESA). Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik, Munic/Garching, Germany, 2019 pp . 64:1–64:14. doi:10.4230/LIPICS.ESA. 2019.64

    work page doi:10.4230/lipics.esa 2019

  20. [20]

    Spanners for Directed Transmission Graphs

    Kaplan H, Mulzer W , Roditty L, Seiferth P . Spanners for Directed Transmission Graphs. SIAM J. Comput.,

    work page

  21. [21]

    doi:10.1137/16M1059692

    47(4):1585–1609. doi:10.1137/16M1059692

    work page doi:10.1137/16m1059692

  22. [22]

    Recognizing Generalized Transmissi on Graphs of Line Segments and Circular Sec- tors

    Klost K, Mulzer W . Recognizing Generalized Transmissi on Graphs of Line Segments and Circular Sec- tors. In: LA TIN. Springer, Buenos Aires, 2018 pp. 683–696. d oi:10.1007/978-3-319-77404-6 50

    work page doi:10.1007/978-3-319-77404-6 2018

  23. [23]

    In 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

    Biniaz A, Bose P , Carmi P , Maheshwari A, Munro JI, Smid MH M. Faster Algorithms for some Opti- mization Problems on Collinear Points. In: Symposium on Com putational Geometry (SoCG). Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, Budapest, Hungary, 2018 pp. 8:1–8:14. doi:10.4230/LIPICS. SOCG.2018.8

    work page doi:10.4230/lipics 2018

  24. [24]

    Planar Formulae and Their Uses

    Lichtenstein D. Planar Formulae and Their Uses. SIAM J. Comput. , 1982. 11(2):329–343. doi:10.1137/ 0211025

    work page 1982

  25. [25]

    Reducibility Among Combinatorial Problems

    Karp RM. Reducibility Among Combinatorial Problems. I n: Complexity of Computer Computations. Plenum Press, New Y ork, USA, 1972 pp. 85–103. doi:10.1007/9 78-1-4684-2001-2 9

    work page doi:10.1007/9 1972