Pith. sign in

REVIEW 4 major objections 5 minor 19 references

Existence and hardness of conveyor belts

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For disks of unequal sizes, deciding whether a conveyor belt exists is NP-complete.

desk verdict Real new results, but both NP-completeness proofs rest on an unproved perturbation claim that a referee should force the authors to prove. read the letter →

arxiv 1908.07668 v1 pith:76Y46EKO submitted 2019-08-21 cs.CG math.CO

Molly Baird , Sara C. Billey , Erik D. Demaine , Martin L. Demaine , David Eppstein , Sándor Fekete , Graham Gordon , Sean Griffin
show 2 more authors
Joseph S. B. Mitchell Joshua P. Swanson
This is my paper · ORCID
classification cs.CGmath.CO MSC 68Q1752C1505C45
keywords conveyorbeltunitdisksNP-completenesscirclepackingbitangentsHamiltoniancycleguidepowerdiagram
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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

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 (4)
  1. [Section 4, Theorem 7 proof] 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).
  2. [Section 4, Theorem 7 proof, integer-input paragraph] 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.
  3. [Section 5, Theorem 10 proof] 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.
  4. [Section 3, Theorem 5 proof] 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.
minor comments (5)
  1. [Section 3, Lemma 4] 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.
  2. [Section 3, Figure 7] 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.
  3. [Section 4, Theorem 7 proof] 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.
  4. [Section 6, Theorem 11 proof] 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.
  5. [Section 6, Theorem 13 proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all load-bearing results come from explicit constructions and standard external theorems; cited prior work enters only as a conjecture to be answered.

full rationale

The paper's derivation chain is self-contained against external benchmarks. The positive results (Theorems 5 and 6) are proved by explicit geometric constructions using the definition of monotonically separated disks, with no fitted parameters and no appeal to the paper's own conclusions. The NP-completeness reductions (Theorems 7 and 10) are built from standard external results: the Koebe–Andreev–Thurston circle packing theorem (cited to Ziegler), Wigderson's NP-completeness result for Hamiltonian cycles in maximal planar graphs, and the Garey–Johnson–Tarjan result for cubic 3-connected planar graphs. The authors' own prior work (Demaine, Demaine, and Palop) appears only as a conjecture to be answered in Theorem 11, not as a load-bearing premise. The shrinkage step in Sections 4 and 5 is asserted informally and may be a genuine proof gap, but it is a geometric existence claim about a sufficiently small delta, not a definitional equivalence or a renamed fit; any weakness there is a correctness risk, not circularity. The power-diagram construction for guide disks is also an explicit algorithm using standard properties of power diagrams. No equation or construction is shown to reduce by definition to the target result, and no fitted input is relabeled as a prediction. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper relies only on standard cited results from graph theory, circle packing, and power diagrams. There are no fitted constants and no exotic postulates. The constructions are fully explicit.

assumptions (6)
  • standard math Koebe-Andreev-Thurston circle packing theorem: every planar graph has a system of interior-disjoint disks tangent according to its adjacency.
    Invoked in Sections 4 and 5 for the NP-completeness reductions to create disk arrangements from planar graphs.
  • standard math Hamiltonian cycle is NP-complete for maximal planar graphs (Wigderson 1982, [16]).
    Used in Theorem 7 for the one-touch NP-hardness reduction.
  • standard math Hamiltonian circuit is NP-complete for cubic 3-connected planar graphs (Garey, Johnson, Tarjan 1976, [11]).
    Used in Theorem 10 for the multi-touch NP-hardness reduction.
  • standard math There exist cubic 3-connected planar graphs whose longest path has fewer than |V|/3 vertices (Grunbaum and Walther 1973, [12]).
    Used in Lemma 12 to prove the linear lower bound on guide disks.
  • standard math For a maximal planar graph the circle packing can be chosen with three given mutually tangent unit disks on the outer face, and all radii bounded below by an exponential factor in the degree (Malitz and Papakostas 1994, [13]).
    Used in Section 4 to argue the shrink factor delta and numerical precision are manageable.
  • standard math Power diagram of a set of disks has linear size and can be constructed in O(n log n) time (Aurenhammer 1987, [4]).
    Used in Theorem 11 to construct guide disks along the dual spanning tree.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Existence and hardness of conveyor belts." pith.science (2026). https://pith.science/paper/76Y46EKO

@misc{pith2026190807668,
  author       = {Pith},
  title        = {Pith review of: Existence and hardness of conveyor belts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/76Y46EKO}},
  note         = {Machine review of arXiv:1908.07668}
}
abstract

An open problem of Manuel Abellanas asks whether every set of disjoint closed unit disks in the plane can be connected by a conveyor belt, which means a tight simple closed curve that touches the boundary of each disk, possibly multiple times. We prove three main results. First, for unit disks whose centers are both $x$-monotone and $y$-monotone, or whose centers have $x$-coordinates that differ by at least two units, a conveyor belt always exists and can be found efficiently. Second, it is NP-complete to determine whether disks of varying radii have a conveyor belt, and it remains NP-complete when we constrain the belt to touch disks exactly once. Third, any disjoint set of $n$ disks of arbitrary radii can be augmented by $O(n)$ "guide" disks so that the augmented system has a conveyor belt touching each disk exactly once, answering a conjecture of Demaine, Demaine, and Palop.

Figures

Figures reproduced from arXiv: 1908.07668 by the authors.

Figure 1
Figure 1. A conveyor belt on 24 nonoverlapping unit disks. The colors and mark￾ings of the disks indicate their orientations. We review some of the history of Abellanas’ question. While Abellanas’ question remains open for unit disks, Tejel and Garc´ıa found an example of non-unit disks that have no conveyor belt [9]. This work was partially supported by the University of Washington Graduate School and grants from the Nationa… view at source ↗
Figure 2
Figure 2. The four possible bitangents between two disks. A conveyor belt for a collection of disks can be specified as follows. Between any two disks, the belt may travel along one of four bitangent line segments. The two disks have the same orientation if the bitangent does not pass through the line connecting their centers and they have different orientations otherwise. We call a bitangent unblocked if it does not intersec… view at source ↗
Figure 3
Figure 3. Diagrams of monotonically separated sequences. For unit disks with indices i < j < k and with centers that are x- and y-monotone (left) or whose x-coordinates differ by at least two units (right), the convex hull of disks i and j is confined to a disjoint region from disk k. Proof. Consider the upper convex hull of the disks, which is the part of the boundary of the convex hull passing clockwise from the leftmost po… view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: The first picture shows the four partial conveyor belts between three adjacent lower disks. The red arc labeled α is required to be part of the final belt. The second picture shows the next iteration of the algorithm after extending the 4 possible belts to include Di+2…
Figure 5
Figure 5. Figure 5: A sequence of x- and y-monotone unit disks and the conveyor belt (red) produced for it by our algorithm. The blue line segments indicate the alternative bitangents found as preliminary results by our algorithm, connecting to the opposite side of each non-upper-hull dis…
Figure 6
Figure 6. Figure 6: shows another example of the final belt constructed in the algorithm where the disks are monotonically separated but not x- and y-monotone [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
Figure 7
Figure 7. Figure 7: Left: A sequence of x- and y-monotone disks with no bitonic conveyor belt. The second-to-last disk in this sequence sorted by x-coordinates of centers (the smallest disk) has no bitangents to the last and largest disk, so it must be a local but not global maximum in th…
Figure 8
Figure 8. Figure 8: A one-touch conveyor belt for a system of disks constructed by slightly shrinking a circle packing for the graph of the edges and vertices of an octahedron. The belt touches the disks in the order given by a Hamiltonian cycle on the octa￾hedron, and crosses between dis…
Figure 9
Figure 9. Figure 9: The four possible patterns for a conveyor belt to enter and exit a triangle of a circle packing with a fourth smaller circle inside it: Two double-ply crossings to adjacent triangles (top left), one double-ply crossing (bottom left), a double-ply and two single-ply cro…
Figure 10
Figure 10. Figure 10: Adding three small disks to the outer triangle of a circle packing re￾stricts a conveyor belt to enter and exit the interior of the packing as shown, up to rotation and reflection. maximal planar graphs used for the one-touch problem. Again, testing Hamiltonicity of t…
Figure 11
Figure 11. Figure 11: A system of n disks requiring Ω(n) guide disks for a one-touch conveyor belt circle packing (choosing arbitrarily which triple of circles to make exterior), place another smaller tangent circle within each triangle of circles of the packing, and then shrink all of the…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 16 canonical work pages

  1. [1]

    Abellanas

    M. Abellanas. Conectando puntos: poligonizaciones y otros problemas relacionados. Gaceta de la Real Sociedad Matematica Espa˜ nola, 11(3):543–558, 2008

    work page 2008

  2. [2]

    Abellanas

    M. Abellanas. Linking geometric objects. In P. Ramos and V. Sacrist´ an, editors, XIV Spanish Meeting on Computational Geometry, In Honor of Ferran Hurtado’s 60th Birthday, Alcal´ a de Henares, June 27–30, 2011 , pages 31–32. Centre de Recerca Matem´ atica, Bellaterra, 2011. URL:https://ddd.uab.cat/pub/llibres/2011/ hdl_2072_200199/Documents08_web.pdf

    work page 2011

  3. [3]

    A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9(5):216–219, 1979. doi:10.1016/0020-0190(79)90072-3

    doi:10.1016/0020-0190(79)90072-3 1979

  4. [4]

    Aurenhammer

    F. Aurenhammer. Power diagrams: properties, algorithms and applications. SIAM J. Comput. , 16(1):78–96,

    work page

  5. [5]

    M. J. Bannister, W. E. Devanny, D. Eppstein, and M. T. Goodrich. The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings. J. Graph Algorithms & Applications, 19(2):619–656, 2015. arXiv:1408.1422, doi:10.7155/jgaa.00349

    work page Pith review arXiv 2015

  6. [6]

    C. R. Collins and K. Stephenson. A circle packing algorithm. Comp. Geom., 25(3):233–256, 2003. doi:10.1016/ S0925-7721(02)00099-8

    work page 2003

  7. [7]

    T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms . MIT Press, 3rd edition, 2009

    work page 2009

  8. [8]

    E. D. Demaine and M. L. Demaine. Fun with fonts: algorithmic typography. Theoret. Comput. Sci., 586:111–119,

    work page

Show all 19 references
  1. [9]

    E. D. Demaine, M. L. Demaine, and B. Palop. Conveyer-belt alphabet. In H. Aardse and A. van Baalen, editors, Findings in Elasticity , pages 86–89. Pars Foundation, Lars M¨ uller Publishers, April 2010

    2010

  2. [11]

    M. R. Garey, D. S. Johnson, and R. E. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5(4):704–714, 1976. doi:10.1137/0205049

    1976 doi

  3. [12]

    Gr¨ unbaum and H

    B. Gr¨ unbaum and H. Walther. Shortness exponents of families of graphs. Journal of Combinatorial Theory. Series A, 14:364–385, 1973. doi:10.1016/0097-3165(73)90012-5

    1973 doi

  4. [13]

    Malitz and A

    S. Malitz and A. Papakostas. On the angular resolution of planar graphs. SIAM J. Discrete Math., 7(2):172–183,

  5. [14]

    B. Mohar. A polynomial time circle packing algorithm. Discrete Math., 117(1–3):257–263, 1993. doi:10.1016/ 0012-365X(93)90340-Y

    1993

  6. [15]

    O’Rourke

    J. O’Rourke. String-wrapped rotating disks. In A. M´ arquez, P. Ramos, and J. Urrutia, editors, XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcal´ a de Henares, Spain, June 27-30, 2011, Revised Sele...

    2011 doi

  7. [16]

    Wigderson

    A. Wigderson. The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical Report 298, Princeton University Department of Computer Science, 1982

    1982

  8. [17]

    G. M. Ziegler. Steinitz’ theorem for 3-polytopes. In Lectures on Polytopes, Lecture 4, pages 103–126. Springer- Verlag, 1995

    1995

  9. [1994]

    doi:10.1137/S0895480193242931

    doi

  10. [2015]

    doi:10.1016/j.tcs.2015.01.054

    2015 doi

  11. [2019]

    URL: http://arxiv.org/abs/1903.04737

    1903 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.