{"id":"22c86099-e334-41bb-9751-c2c56598fd19","arxiv_id":"1908.07668","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For monotonically separated unit disks a conveyor belt always exists; for variable radii the decision problem is NP-complete; O(n) guide disks always suffice.","lead":"This paper studies conveyor belts, tight closed curves that touch each disk in a collection of non-overlapping disks. It proves existence for certain unit-disk layouts, shows the problem becomes NP-complete when disk sizes vary, and proves a linear number of 'guide' disks always suffices.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The NP-hardness reductions hinge on an unproved perturbation lemma: after shrinking a circle packing, only formerly tangent disk pairs have unblocked bitangents; without a uniform-δ proof, the Hamiltonian-cycle equivalence may fail.","rationale":"The reader's weakest_assumption points to the same step I identify. I agree: the shrunken-circle-packing bitangent claim is the single most load-bearing unproved assertion. The rest of the positive results (Theorems 5, 6, 11, 13) are independent of this lemma and appear sound: Theorems 5 and 6 have a constructive proof, and the guide-disk constructions use power diagrams in a more robust way. The NP-hardness reductions are the central contribution, so a gap there matters. I do not see a concrete counterexample, and the claim is plausible; however, the proof as written is incomplete. A referee should ask for a formal lemma with a proof (or a reference to a known lemma) establishing that the visibility graph of a uniformly shrunken circle packing equals the contact graph. The numerical-precision concern raised by the reader is likely addressable via the Malitz-Papakostas exponential radius-ratio bound, but the blocking threshold issue is not addressed by that bound. Hence I recommend CONDITIONAL rather than REJECT: accept if the perturbation lemma can be supplied; the stated theorems otherwise lack a necessary proof.","tokens_in":11643,"tokens_out":25652,"duration_ms":224464,"concrete_test":"Use existing circle-packing software to compute the circle packing for a battery of small maximal planar graphs, including Wigderson's 58-vertex gadget and the octahedron. For each graph, compute all bitangents between every pair of disks in the shrunken packing for δ = 10^{-1}, 10^{-2}, ..., 10^{-12} and test each bitangent for intersection with every other disk. Record the infimal δ at which any non-adjacent pair first becomes visibly connected. If this infimum is 0 for some graph, the perturbation lemma is false and the reduction collapses. If it is always positive, compute how it scales with n; a positive bound for all tested graphs would support the lemma but still leave the proof incomplete, indicating the paper should be revised to supply that proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing step is the claim in Section 4 (and reused in Section 5) that after uniformly shrinking each disk of the circle packing by 1−δ, 'the only unblocked bitangents are between pairs of disks that were tangent before shrinking.' This is asserted informally, with Figure 8, but no proof is supplied. The reduction's correctness requires the bitangent-visibility graph of the shrunken disks to equal the contact graph of G (plus the three outer-face tangents): in the belt-to-Hamiltonian direction, the belt can only move along unblocked bitangents, so if any non-adjacent pair becomes visible, a belt might exist even when G is non-Hamiltonian. The existence of a single δ that simultaneously blocks every non-adjacent pair is not immediate: for each such pair, there may be a threshold δ* at which some bitangent first clears all intervening disks, and the paper does not bound these thresholds away from zero. In particular, a bitangent between non-adjacent disks that is tangent to an intermediate disk at δ=0 could in principle become unblocked for every δ>0; the paper's continuity-based intuition does not rule this out. The later sentence bounding δ by 'a polynomial in the smallest possible ratio εn between tangent disks' addresses numerical representation but not the geometric blocking condition. Since both NP-completeness theorems (Theorems 7 and 10) depend on this lemma, the central hardness claim is not yet fully supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the conveyor-belt problem for disjoint disks: deciding whether a tight simple closed curve can touch every disk while avoiding their interiors. It contributes three groups of results. First, it proves that monotonically separated configurations of unit disks always admit a conveyor belt constructible in linear time after sorting (Theorems 5 and 6), and it observes that this includes xy-monotone and x-separated configurations. Second, it proves NP-completeness for the one-touch version of the problem (Theorem 7) and for the general multi-touch version (Theorem 10), via reductions from Hamiltonian cycle problems using circle packings. Third, it shows that any disk configuration can be augmented by O(n) guide disks so that a one-touch conveyor belt exists, answering a conjecture of Demaine, Demaine, and Palop (Theorem 11), and that Omega(n) guide disks are sometimes necessary (Theorem 13).","tokens_in":11887,"tokens_out":6246,"duration_ms":606570,"significance":"If the results are correct, the paper substantially advances the understanding of Abellanas' open problem: it gives the first hardness results for conveyor belts on non-unit disks, while providing positive algorithmic results for relevant families of unit-disk configurations. The guide-disk theorems are also interesting and give a sharp asymptotic answer to a previously open question. The paper is constructive and uses standard tools such as the Koebe-Andreev-Thurston theorem, power diagrams, and classical NP-completeness reductions. The asymptotic bounds in Theorems 11 and 13 are clean and, if the proofs are completed, would be a notable contribution. The main weakness is that the geometric perturbation arguments underlying the NP-hardness reductions are asserted informally rather than proved, and the same applies to part of the constructive proof of Theorem 5; these are gaps in the current write-up rather than demonstrated errors.","major_comments":[{"comment":"The reduction's correctness hinges on the assertion that, after shrinking every disk of the circle packing by a factor of 1-delta, 'the only unblocked bitangents are between pairs of disks that were tangent before shrinking' (paragraph beginning 'The reduction begins,' with Figure 8). This claim is load-bearing for the belt-to-Hamiltonian direction, but no proof is supplied. In particular, the text does not rule out the possibility that for some non-adjacent pair of disks a bitangent becomes unblocked for every positive delta, nor does it give a uniform lower bound on delta that simultaneously blocks all non-adjacent pairs. The subsequent discussion bounding delta in terms of the smallest radius ratio addresses numerical precision, but not the geometric blocking condition. Please provide a formal perturbation lemma establishing the existence of a delta > 0 for which the bitangent-visibility graph of the shrunken disks is exactly the contact graph of the packing (plus the three outer tangents).","section":"Section 4, Theorem 7 proof"},{"comment":"The reduction is required to produce a system of disks specified by integer center coordinates and radii, but the proof only says that an approximate numerical representation of the circle packing can be scaled 'appropriately' to make the coordinates and radii integers. Scaling a numerical approximation destroys the exact tangencies on which the subsequent argument relies, and no robustness or stability lemma is provided to show that the resulting integer instance has the same bitangent-visibility properties as the exact shrunken packing. This is a separate gap from the missing perturbation lemma and affects both NP-completeness theorems, since Theorem 10 inherits the reduction framework.","section":"Section 4, Theorem 7 proof, integer-input paragraph"},{"comment":"The proof of Theorem 10 depends on a case analysis over the configurations in Figures 9 and 10, with assertions such as 'by inspecting each case' and 'the interior connections must then all be double-ply as well.' The dichotomy between single-ply and double-ply crossings, and the exclusion of the middle and right configurations in Figure 10, are essential for the equivalence with Hamiltonian cycles of the dual cubic graph. These claims are currently justified only by pictorial inspection rather than by a complete geometric argument. Please replace the figure-based inspection with a formal enumeration of the possible belt configurations, including a proof that the depicted cases are exhaustive.","section":"Section 5, Theorem 10 proof"},{"comment":"The winding and unwinding processes are described algorithmically, but the proof that the produced partial belts are valid (property (c)) is compressed into statements such as 'every property is clear except possibly...' and 'by construction,' and the pasting step for four partial belts is justified by 'one may check.' Since Theorem 5 is one of the main positive results of the paper, these claims should be expanded into a complete argument, in particular the assertion that the partial belts do not self-intersect and remain disjoint from all disk interiors.","section":"Section 3, Theorem 5 proof"}],"minor_comments":[{"comment":"In the proof of Lemma 4, the xy-monotone case is dismissed with 'the other cases are similar.' An explicit separating-line argument for that case would improve readability and make the lemma self-contained.","section":"Section 3, Lemma 4"},{"comment":"The text says that the second-to-last disk in the left example 'has no bitangents to the last and largest disk.' Since every two disjoint disks have four bitangent line segments, the intended meaning is 'no unblocked bitangent'; the wording should be adjusted.","section":"Section 3, Figure 7"},{"comment":"The NP-membership part says that a solution can be described in O(n log n) bits and verified with O(n^2) tests. Since the input disks have integer coordinates but bitangent contact points may be algebraic, the verification should specify how exact comparisons are performed; otherwise the claim is not fully justified.","section":"Section 4, Theorem 7 proof"},{"comment":"The construction of guide disks is described as adding 'small guide disks near x, y, and z as needed.' The proof should specify how small is sufficient and argue that the new disks do not interfere with the already-constructed belt segments or with each other.","section":"Section 6, Theorem 11 proof"},{"comment":"For the one-touch lower bound, the regular-polygon arrangement of small disks around a large central disk needs a short argument that the specified radii can be chosen so that no two small disks have an unblocked bitangent; the current text only asserts this.","section":"Section 6, Theorem 13 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong contribution and the identified gaps appear to be fillable rather than fundamental. In particular, the missing perturbation lemma in Sections 4 and 5 is the central issue: without a proof that a uniform delta exists and that the integer-input construction preserves the bitangent-visibility graph, the NP-completeness claims are not yet established. I recommend major revision rather than rejection, but the revision must add the missing geometric lemmas rather than only stylistic changes. The positive results and guide-disk theorems are likely sound and valuable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one: it is a genuine contribution with three new results, but the two NP-completeness proofs share a gap that a referee should not wave through.\n\nWhat I like. The existence theorem for monotonically separated unit disks (Theorem 5) is new, and the winding-process construction is clean; the linear-time version is a nice bonus. The guide-disk theorem (Theorem 11) answers a real conjecture, and the power-diagram construction is sound. The lower bound in Theorem 13 is simple but effective. The paper is honest that the original Abellanas question for unit disks remains open.\n\nThe soft spot is the perturbation lemma in Section 4, reused in Section 5. The proof says that after shrinking a circle packing by 1−δ, the only unblocked bitangents are between disks that were tangent before shrinking, and points to Figure 8. That is exactly the load-bearing step for the Hamiltonian-cycle equivalence, and it is not proven. A bitangent between two non-adjacent disks that happens to be tangent to an intermediate disk at δ=0 becomes unblocked for any δ>0 once that intermediate disk shrinks. The text about δ being polynomial in the radius ratio addresses numeric representation, not this geometric blocking issue. It may well be that maximal planar circle packings are dense enough to forbid such a configuration, but the paper needs to say why. Right now the hardness theorems are conditional on an unstated geometric fact.\n\nThe rest of the proofs are sketches—case inspection in Section 5, 'one may check' in Section 3—but they are the kind of sketches that are standard for this community, and the figures make the intent clear. I do not see circular reasoning or fitted parameters; the citation pattern is fine.\n\nRecommendation: serious referees should see this, but the likely outcome should be 'revise.' Ask for a formal proof of the shrinking/bitangent lemma before the NP-completeness results are considered established. If that lemma is supplied, this is a solid SoCG-level paper.","headline":"Real new results, but both NP-completeness proofs rest on an unproved perturbation claim that a referee should force the authors to prove.","tokens_in":12455,"tokens_out":15993,"would_cite":true,"duration_ms":224119,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","52C15","05C45"],"pacs":[],"model":"deepseek-v4-flash","headline":"For disks of unequal sizes, deciding whether a conveyor belt exists is NP-complete.","keywords":["conveyor belt","unit disks","NP-completeness","circle packing","bitangents","Hamiltonian cycle","guide disks","power diagram"],"falsifier":"Run the contraction on a circle packing of a maximal planar graph known to have no Hamiltonian cycle; if an exact geometric computation finds a valid conveyor belt in the shrunken configuration, the claimed equivalence between belts and Hamiltonian cycles is false. Equivalently, exhibit any two non-adjacent disks whose shrunken packing admits an unblocked bitangent.","tokens_in":11440,"feed_emoji":"🛞","tokens_out":4826,"duration_ms":45269,"temperature":0.7,"pith_summary":"The paper studies Abellanas' open question: can every finite collection of disjoint disks be wrapped by a tight simple closed curve that touches every disk? It establishes that two positive classes of unit disks—monotonically separated configurations, which include centers that are both x- and y-monotone and centers with horizontal gaps of at least two units—always have such a conveyor belt, and a belt can be constructed in linear time. It then proves that allowing disks of arbitrary radii makes the decision problem NP-complete, even when the belt is required to touch each disk exactly once. Finally, adding $O(n)$ extra guide disks always creates a one-touch belt, and some configurations genuinely need $\\Omega(n)$ of them.","feed_headline":"Unequal disks make conveyor-belt checks NP-complete","feed_subtitle":"Monotone unit disks always admit a belt; deciding existence for varied radii is computationally hard.","key_machinery":"The conveyor belt itself is the central object: a continuously differentiable simple closed curve made of circular arcs on disk boundaries and bitangent segments between disks, disjoint from all disk interiors. The hardness reductions rest on the circle packing theorem, which represents a planar graph as tangent disks, followed by a uniform shrinkage so small that unblocked bitangents exist only between formerly tangent pairs; then belts correspond exactly to Hamiltonian cycles in the graph. The positive results use a winding process over monotonically separated disks, and the guide-disk construction uses the power diagram and a spanning tree of its dual graph.","core_discovery":"The central claim is a tripartite answer to Abellanas' problem. For unit disks whose centers are xy-monotone or whose x-coordinates differ by at least two units, a conveyor belt always exists and can be computed in linear time after sorting. For disks of arbitrary radii the existence problem is NP-complete, both in the multi-touch version and in the one-touch version, via reductions from Hamiltonian cycle in maximal planar graphs and in cubic 3-connected planar graphs. Finally, any configuration of $n$ disks can be augmented by $O(n)$ extra guide disks so that a one-touch conveyor belt exists, and this linear bound is tight up to a constant because some configurations require $\\Omega(n)$ guides.","pith_inferences":["This reader infers that if the shrinking premise behind the reductions is made fully rigorous with explicit bit bounds, the result becomes a formal NP-completeness proof for a purely geometric decision problem; the paper's informal argument leaves room for a more careful accounting.","This reader infers that the near-parsimonious reduction makes it likely that counting distinct conveyor belts is #P-hard, though the paper leaves that question open.","This reader infers that the monotone-separation sufficient condition may extend to non-unit disks under a similar separation hypothesis; the paper only constructs counterexamples to bitonic belts for nonunit disks.","This reader infers that a natural testable extension is to lower the x-separation threshold from two units toward the minimal kissing distance, or to characterize the minimum separation that guarantees a belt."],"forward_implications":["For every xy-monotone set of unit disks, a conveyor belt exists and is efficiently constructible, settling Abellanas' question for that restricted class.","The general unit-disk question remains open; these results neither prove nor disprove it, but they locate the computational hardness in ratios between radii.","The one-touch variant, a cleaner combinatorial version of the problem, is computationally intractable in general.","Any disk packing can be made belt-enabled by adding a linear number of guide disks, and some packings genuinely need that many.","The reductions provide geometric certificates of Hamiltonian cycles: belts encode tours, so finding belts is at least as hard as finding those cycles."],"supporting_citations":[{"why":"states the Koebe–Andreev–Thurston circle packing theorem used to represent planar graphs as tangent disks.","marker":"[17]"},{"why":"supplies NP-completeness of Hamiltonian cycle in maximal planar graphs, the reduction source for one-touch belts.","marker":"[16]"},{"why":"supplies NP-completeness of Hamiltonian cycle for cubic 3-connected planar graphs, used for multi-touch belts via duality.","marker":"[11]"},{"why":"gives the exponential bound on radius ratios in circle packings that controls the shrink factor's bit complexity.","marker":"[13]"},{"why":"defines the power diagram whose dual spanning tree organizes the guide-disk construction.","marker":"[4]"},{"why":"provides the linear-time Andrew convex hull scan used in the monotone belt construction.","marker":"[3]"},{"why":"records the Demaine–Demaine–Palop conjecture and the earlier non-unit counterexample that the guide-disk theorem answers.","marker":"[9]"},{"why":"provides a polynomial-time circle packing algorithm used to construct the disk systems in the reductions.","marker":"[14]"}],"fun_headline_variants":["Conveyor belts are NP-complete for varied disk radii","Monotone unit disks guarantee conveyor belts efficiently","O(n) guide disks always enable one-touch belts","Abellanas belt problem: easy for monotone, hard for general","Varied radii make belt existence NP-complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hardness proof assumes that a circle packing of a maximal planar graph can be shrunk by a tiny amount so that the only newly unblocked bitangents are between disks that were tangent before shrinking, and that this configuration can be represented with polynomially many bits.","fun_headline_variants_meta":{"raw":{"variants":["Conveyor belts are NP-complete for varied disk radii","Monotone unit disks guarantee conveyor belts efficiently","O(n) guide disks always enable one-touch belts","Abellanas belt problem: easy for monotone, hard for general","Varied radii make belt existence NP-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000248,"raw_usage":{"total_tokens":1497,"prompt_tokens":843,"completion_tokens":654,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":573}},"tokens_in":459,"tokens_out":654,"duration_ms":7181,"temperature":1.0,"reasoning_tokens":573,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:59:39.077627+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the contraction on a circle packing of a maximal planar graph known to have no Hamiltonian cycle; if an exact geometric computation finds a valid conveyor belt in the shrunken configuration, the claimed equivalence between belts and Hamiltonian cycles is false. Equivalently, exhibit any two non-adjacent disks whose shrunken packing admits an unblocked bitangent.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"states the Koebe–Andreev–Thurston circle packing theorem used to represent planar graphs as tangent disks."},{"cited_title":"Wigderson","cited_arxiv_id":null,"evidence_quote":"supplies NP-completeness of Hamiltonian cycle in maximal planar graphs, the reduction source for one-touch belts."},{"cited_title":"Malitz and A","cited_arxiv_id":null,"evidence_quote":"gives the exponential bound on radius ratios in circle packings that controls the shrink factor's bit complexity."},{"cited_title":"Aurenhammer","cited_arxiv_id":null,"evidence_quote":"defines the power diagram whose dual spanning tree organizes the guide-disk construction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"records the Demaine–Demaine–Palop conjecture and the earlier non-unit counterexample that the guide-disk theorem answers."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides a polynomial-time circle packing algorithm used to construct the disk systems in the reductions."}],"review_version":1}