Pants Decomposition of the Punctured Plane

Computer Science; Sheung-Hung Poon (1); Shripad Thite (1) ((1) Department of Mathematics; Technische Universiteit Eindhoven; the Netherlands)

REVIEW

Pants Decomposition of the Punctured Plane

Sheung-Hung Poon (1), Shripad Thite (1) ((1) Department of Mathematics, Computer Science, Technische Universiteit Eindhoven, The Netherlands)

Computational Geometry · Submitted 22 Feb 2006 · 9 references

Pith's verdict: A promising research sketch on minimum-length pants decompositions with a plausible but unproved PTAS and degenerate-DP recurrences; not publishable as is, but worth a serious referee to force the proofs.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 4 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDcs/0602080 (version 1)

Pith ID533QKTJ3, Pith's permanent record of this paper and its review

CitationComputer Science, Sheung-Hung Poon (1), Shripad Thite (1) ((1) Department of Mathematics, Technische Universiteit Eindhoven, the Netherlands). "Pants Decomposition of the Punctured Plane." arXiv:cs/0602080 (2006). https://pith.science/paper/533QKTJ3

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Colleague,

The paper is a research sketch, not a finished paper. The new thing is the problem formulation — global minimum-length pants decomposition of the punctured plane — plus a TSP lower bound and an O(log n) approximation that are straightforward but correct. The exact DP for points on a line has a natural recurrence, and the box version is a plausible follow-up. The PTAS is the headline claim, and it is not proven.

What is actually new: nobody had formulated this optimization problem before, and the observation that a shortest pants decomposition contains a TSP tour, and conversely a TSP tour can be converted to a pants decomposition of length O(log n) times optimal, is a nice starting point. The DP for the line case, with Yao speedup, is a clean exercise (though the recurrence has a subtle issue, see below). The authors are honest: they label Section 6 as work in progress.

The soft spots are serious. The PTAS rests on two structural assertions: that an optimal pants decomposition admits a sequence of favorable guillotine cuts with small total bridge length, and that cycles can be rerouted through O(M) portals per rectangle. The paper gives no proof for either. Mitchell's theorem applies to a single tour or subdivision, not to a family of Θ(n) nested cycles. The sentence “Intuitively, we can bend…” is not a lemma. The claimed approximation factor O(1+2√2/m) is stated without derivation. Without these, the PTAS has no correctness proof.

The line recurrence is also problematic. The length 2(xj−xi) for the outermost cycle is an infimum over zero-width curves, not a length attained by a simple cycle. So c(i,j) as defined is not a minimum. The convexity proof that leads to the recurrence is hand-wavy; the swaps may create crossings or change the nesting structure in ways not accounted for. The box recurrence inherits these issues and has no separate justification.

This does not mean the ideas are worthless. The PTAS may be fixable with a more careful transfer argument, and the DP recurrences might be repaired by defining cycles in terms of limiting curves or by allowing degenerate cycles with a caveat. But as it stands, the paper is not publishable in its current form.

Who is this for? Researchers in computational topology and geometric optimization who want to see a plausible direction for minimum-length pants decompositions. It could serve as a pointer to open problems, not as a citable result. I would bring it to a reading group if we wanted to brainstorm how to prove the guillotine property for nested cycles, but I would not cite it as a source of theorems.

For peer review: a serious referee could give the authors a roadmap to complete the proofs, so I would send it out despite expecting heavy revision. It is a legitimate research contribution in the making, but the current manuscript needs major work before it is a paper.

Referee report

Major objections (4)

[Section 3, PTAS] The correctness of the PTAS is not established. The algorithm requires two structural lemmas: (i) a shortest pants decomposition admits a recursive sequence of favorable cuts whose total bridge length is at most (sqrt(2)/m)|Pi*|, and (ii) every cycle of Pi* can be bent so that it crosses each subproblem rectangle boundary only at O(M) portals with bounded length increase. Mitchell's theorem proves these properties for a single rectilinear tour or subdivision, but the paper does not prove either property for a family of Theta(n) pairwise-nested cycles. The sentence 'Intuitively, we can bend the cycles...' is not a proof. The final approximation factor O(1 + 2 sqrt(2)/m) is also stated without derivation from the bridge bound and portal costs. Without these missing lemmas, the PTAS is not a correctness proof.
[Section 4, Points on a line] The recurrence c(i,j) = 2(x_j - x_i) + min_k (c(i,k) + c(k+1,j)) is not well-posed as stated. For collinear punctures, a simple cycle enclosing a contiguous interval of points has length strictly greater than 2(x_j - x_i); the value 2(x_j - x_i) is only an infimum over cycles of arbitrarily small width, not the length of an actual simple cycle in Sigma = E^2 \ P. Thus a shortest decomposition may not exist, and the dynamic program computes an infimum rather than a minimum. The paper must either prove existence of the shortest decomposition under its definition of non-crossing, or explicitly allow degenerate zero-width cycles and adjust the definition accordingly.
[Section 4, exchange argument] The claim that a shortest non-crossing pants decomposition on collinear points consists only of convex cycles is not fully proved. The exchange argument describes replacing cycles C1 and D_{i-1} or C2 and D_{i-1}, but it does not verify that the modified cycles remain simple, pairwise non-crossing, and homotopically valid, nor does it provide a metric inequality showing the new total length is strictly smaller. These details are essential because the recurrence (1) depends on the decomposition being recursively decomposable into contiguous intervals.
[Section 5, Box decomposition] The box decomposition recurrence is asserted to be 'similar' to the one-dimensional case, but no proof is given that a shortest box decomposition has the required optimal substructure. The observation that any two axis-aligned rectangles are separable by a horizontal or vertical line does not by itself imply that an outermost box in an optimal decomposition splits the point set into two independent subproblems. Additionally, the claimed running time O(n^4) relies on a two-dimensional version of Yao's speedup, but the paper does not prove the monotonicity of the optimal split pair or the relevant quadrangle inequality for the two-dimensional cost function. Without these proofs, the O(n^4) claim is unsupported.

Minor objections (4)

[Section 2] The claim that each tour edge appears in at most ceil(log n) cycles is asserted without proof. A short argument showing that the greedy merge order controls the depth of each edge would make the O(log n) approximation self-contained.
[Section 1] The definition says a pants decomposition is 'a collection of disjoint cycles,' while the non-crossing definition later allows cycles to touch. These two statements should be reconciled explicitly.
[Section 5] In the definition of the diagonal order, 'max{i2 - i1, j2 - j - 1}' appears to contain a typo; it should likely be 'j2 - j1'. Please correct this.
[Throughout] There are several typographical issues, including 'W e call', 'na¨ive', and inconsistent font spacing. A careful proofreading pass is needed.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper presents a polynomial-time approximation scheme for shortest pants decompositions of the punctured plane, plus exact polynomial algorithms for box-restricted and collinear point sets.

The reading

The paper is trying to establish that the optimization problem of cutting the plane minus n punctures into pairs of pants (genus-zero surfaces with three boundary components) by simple cycles of minimum total length is tractable in a strong sense. It claims a polynomial-time approximation scheme: for any fixed ε>0, a decomposition within factor 1+ε of optimal can be computed in time polynomial in n. It also claims exact polynomial algorithms for two restricted versions: when all cycles are required to be axis-aligned rectangles, the shortest decomposition is computed in O($n^{4}$) time, and when all punctures lie on one line, in O($n^{2}$) time. Both exact algorithms are based on dynamic programming with a quadrangle-inequality speedup. The results matter because they turn a topological optimization problem with Θ(n) interacting cycles into provably efficient computation, and because they make concrete the geometry that governs optimal pants decompositions.

What carries the argument

The central object is a pants decomposition: a collection of disjoint simple cycles that cut the punctured plane into pairs of pants, surfaces of genus zero with three boundary cycles. The paper uses the nesting structure of these cycles, which forms a binary tree with n leaves, to set up recursive decompositions. For approximation, the load-bearing mechanism is the guillotine rectilinear subdivision: recursively split the bounding box by horizontal or vertical cuts, route cycles through O(M) prescribed crossing points, or portals, on each cut, and charge the added detour length with a portal-count bound. For exactness, the key identity is a concave quadrangle inequality in the cost function, which gives monotonicity of optimal split points and allows dynamic programming with a linear-factor speedup.

Extended reading notes

Core claim

The paper's central claim is that the shortest pants decomposition of the punctured plane can be approximated within a factor 1+ε in polynomial time for any fixed ε>0, by adapting the guillotine-rectilinear-subdivision dynamic program for Euclidean TSP, and that exact solutions are computable in polynomial time for two restricted settings: O($n^{4}$) when every cycle must be an axis-aligned box, and O($n^{2}$) when the punctures lie on one line. In the line case, the paper proves the optimal decomposition can be assumed convex, yielding the recurrence c(i,j)=2(x_j-x_i)+min_{i≤k<j}(c(i,k)+c(k+1,j)), and uses the concavity of the interval cost to speed up the dynamic program by a linear factor. The box case is the two-dimensional analogue with perimeter cost and the same speeding technique. These are presented as the first polynomial-time approximation and exact results for this minimization problem.

Load-bearing premise

The PTAS rests on the assumption that a horizontal or vertical cut can always be found so that the optimal pants decomposition, after a small bending of its cycles, crosses the cut through only a constant number of prescribed points, adding little length; the paper asserts this holds by analogy with Euclidean TSP but does not prove it.

Editorial extensions

If this is right

For any fixed ε>0, a pants decomposition within factor 1+ε of optimal can be computed in time polynomial in n, so the problem has a polynomial-time approximation scheme.
For collinear punctures, the shortest non-crossing pants decomposition can be computed in O(n^2) time, and its cycles can be taken convex.
For axis-aligned box cycles, the shortest pants decomposition can be computed in O(n^4) time, showing that this restricted version is polynomial-time solvable exactly.
Every shortest pants decomposition is at least as long as a shortest Euclidean TSP tour through the punctures, and any TSP tour converts to a pants decomposition of length at most 2⌈log n⌉ times the tour length, yielding a simple O(log n)-approximation algorithm.
The portal-based PTAS remains polynomial-time even though a pants decomposition contains Θ(n) cycles, because each subproblem carries only polynomially many crossing patterns.

Reading between the lines

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

If the missing structural proof can be supplied, the same guillotine-portal template should carry over to weighted punctures or other polygonal cost metrics, since the argument only needs bounds on how much a cycle detours to reach a portal.
The TSP lower bound suggests that an exact algorithm for the general problem would have to overcome the same combinatorial obstacles as Euclidean TSP; a natural next test is to search for a reduction from Euclidean TSP to pants decomposition that would show NP-hardness.
The collinear recurrence is structurally identical to optimal binary search tree parenthesization, so known O(n^2) algorithms could be reused to reconstruct not only lengths but the actual tree of nested cycles.
A concrete way to test the exact algorithms is to brute-force small instances, say n≤10, and compare with the dynamic-programming outputs; for the PTAS, the missing piece is an explicit counterexample search for the transfer of the favorable-cut lemma to cycles of a pants decomposition.

Original abstract

A pants decomposition of an orientable surface S is a collection of simple cycles that partition S into pants, i.e., surfaces of genus zero with three boundary cycles. Given a set P of n points in the plane, we consider the problem of computing a pants decomposition of the surface S which is the plane minus P, of minimum total length. We give a polynomial-time approximation scheme using Mitchell's guillotine rectilinear subdivisions. We give a quartic-time algorithm to compute the shortest pants decomposition of S when the cycles are restricted to be axis-aligned boxes, and a quadratic-time algorithm when all the points lie on a line; both exact algorithms use dynamic programming with Yao's speedup.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,661 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.46 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.86 · compares with prior results 0.09 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

A pants decomposition of an orientable surface S is a collection of simple cycles that partition S into pants, i.e., surfaces of genus zero with three boundary cycles. Given a set P of n points in the plane, we consider the problem of computing a pants decomposition of the surface S which is the plane minus P, of minimum total length. We give a polynomial-time approximation scheme using Mitchell's guillotine rectilinear subdivisions. We give a quartic-time algorithm to compute the shortest pants decomposition of S when the cycles are restricted to be axis-aligned boxes, and a quadratic-time algorithm when all the points lie on a line; both exact algorithms use dynamic programming with Yao's speedup.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	A pants decomposition of an orientable surface S is a collection of simple cycles that partition S into pants, i.e., surfaces of genus zero with three boundary cycles.	background 1.00	0.06	0.04	asserted 1.00
s1	Given a set P of n points in the plane, we consider the problem of computing a pants decomposition of the surface S which is the plane minus P, of minimum total length.	background 0.87	0.22	0.08	asserted 0.80
s2	We give a polynomial-time approximation scheme using Mitchell's guillotine rectilinear subdivisions.	contribution 0.75	0.94	0.31	asserted 1.00
s3	We give a quartic-time algorithm to compute the shortest pants decomposition of S when the cycles are restricted to be axis-aligned boxes, and a quadratic-time algorithm when all the points lie on a line; both exact algorithms use dynamic programming with Yao's speedup.	contribution 0.90	0.95	0.18	asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.96 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** (i) A pants decomposition of the plane punctured by a set of 6 points, and (ii) the corresponding binary tree. A cycle C on Σ is essential if it does not bound a disk or an annulus. A pants decomposition, also called a maximal cut system [3], is naturally obtained by the following greedy procedure. Let C be an essential cycle. Cut Σ along C to get a surface Σ′ with two additional boundary cycles C1 and C2 corresponding to the two sides of the cut. The cycles C1 and C2, together with the set of cycles obtained by recursing on Σ′ , is a pants decomposition Π of Σ. The resulting cycle…

Figures reproduced from arXiv:cs/0602080 by the authors.

References

Works cited (9)

[1]

S. Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geomet- ric Problems. J. ACM, 45(5):753–782, 1998

View on Pith 1998
[2]

´E. Colin de Verdi` ere, F. Lazarus. Optimal Pants De- compositions and Shortest Homotopic Cycles on an Orientable Surface. Proc. Graph Drawing, pp. 478– 490, 2003. Preliminary version at EuroCG’03

View on Pith 2003
[3]

A. Hatcher. Pants Decompositions of Surfaces. arXiv:math.GT/9906084; http://arxiv.org/abs/math.GT/9906084

View on Pith arXiv
[4]

K. Mehlhorn. Data Structures and Algorithms 1: Sort- ing and Searching . EATCS Monographs on Theoret. Comput. Sci., Springer-Verlag, 1984

View on Pith 1984
[5]

J. S. B. Mitchell. Guillotine Subdivisions Approxi- mate Polygonal Subdivisions: A Simple Polynomial- Time Approximation Scheme for Geometric TSP, k- MST, and Related Problems. SIAM J. Computing, 28(4):1298–1309, 1999

View on Pith 1999
[6]

J. S. B. Mitchell. Approximation Algorithms for Geo- metric Optimization Problems. Proc. Canadian Conf. Comput. Geom., pp. 229–232, 1997

View on Pith 1997
[7]

C. H. Papadimitriou, K. Steiglitz. Combinatorial Op- timization: Algorithms and Complexity . Prentice Hall, 1982

View on Pith 1982
[8]

S. Thite. Optimum Binary Search Trees on the Hierar- chical Memory Model. M.S. thesis, Computer Sci., U. Illinois at Urbana-Champaign, CSL Tech. Rep. UILU- ENG-00-2215 ACT-142, 2000. 4

View on Pith 2000
[9]

F. F. Yao. Speed-up in Dynamic Programming. SIAM J. Algebraic Discrete Methods, 3(4):532–540, 1982. 5

View on Pith 1982

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

S. Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geomet- ric Problems. J. ACM, 45(5):753–782, 1998

View on Pith 1998

[2] [2]

´E. Colin de Verdi` ere, F. Lazarus. Optimal Pants De- compositions and Shortest Homotopic Cycles on an Orientable Surface. Proc. Graph Drawing, pp. 478– 490, 2003. Preliminary version at EuroCG’03

View on Pith 2003

[3] [3]

A. Hatcher. Pants Decompositions of Surfaces. arXiv:math.GT/9906084; http://arxiv.org/abs/math.GT/9906084

View on Pith arXiv

[4] [4]

K. Mehlhorn. Data Structures and Algorithms 1: Sort- ing and Searching . EATCS Monographs on Theoret. Comput. Sci., Springer-Verlag, 1984

View on Pith 1984

[5] [5]

J. S. B. Mitchell. Guillotine Subdivisions Approxi- mate Polygonal Subdivisions: A Simple Polynomial- Time Approximation Scheme for Geometric TSP, k- MST, and Related Problems. SIAM J. Computing, 28(4):1298–1309, 1999

View on Pith 1999

[6] [6]

J. S. B. Mitchell. Approximation Algorithms for Geo- metric Optimization Problems. Proc. Canadian Conf. Comput. Geom., pp. 229–232, 1997

View on Pith 1997

[7] [7]

C. H. Papadimitriou, K. Steiglitz. Combinatorial Op- timization: Algorithms and Complexity . Prentice Hall, 1982

View on Pith 1982

[8] [8]

S. Thite. Optimum Binary Search Trees on the Hierar- chical Memory Model. M.S. thesis, Computer Sci., U. Illinois at Urbana-Champaign, CSL Tech. Rep. UILU- ENG-00-2215 ACT-142, 2000. 4

View on Pith 2000

[9] [9]

F. F. Yao. Speed-up in Dynamic Programming. SIAM J. Algebraic Discrete Methods, 3(4):532–540, 1982. 5

View on Pith 1982