arxiv: 2604.15247 · v1 · submitted 2026-04-16 · 💻 cs.CG

Recognition: unknown

Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

Jaehoon Chung

Authors on Pith no claims yet

Pith reviewed 2026-05-10 08:31 UTC · model grok-4.3

classification 💻 cs.CG

keywords polygonslowermathbfalgorithmstimeversionboundslattice

0 comments

The pith

O(log n) value and O(h log(1+n/h)) reporting algorithms for convex polygons, O(n log n) for simple and self-overlapping polygons, with matching lower bounds, via antichain DP in the Clarke-Cormack-Burkowski lattice.

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

Imagine slicing a shape with straight parallel cuts so every slice is no wider than one unit in a chosen direction. The goal is to use as few slices as possible. The authors model possible cut positions as intervals inside a mathematical lattice originally built for search engines. They then use the lattice's meet and join operations inside a dynamic program to pick the best set of cuts. For convex shapes this runs in logarithmic time; for shapes that cross themselves it still runs in near-linear time, and they prove you cannot do asymptotically better.

Core claim

For convex polygons we solve the value version in O(log n) time and the reporting version in O(h log(1 + n/h)) time with matching decision-tree lower bounds; for simple polygons O(n log n) time and O(n) space with Omega(n) lower bound; for self-overlapping polygons the same time bound with Omega(n log n) algebraic computation-tree lower bound via reduction from delta-closeness.

Load-bearing premise

Strip partitions of the input polygon can be faithfully represented as antichains of intervals in the Clarke-Cormack-Burkowski lattice so that the lattice meet and join operations correctly compute the minimum partition.

Figures

Figures reproduced from arXiv: 2604.15247 by Jaehoon Chung.

**Figure 1.** Figure 1: (a) The polygon P has a windmill shape with three arms extending from an equilateral triangle of height 4. (b) A minimum partition of P under width and cut constraints, W = U = S +. (c) A minimum orthogonal strip partition of P with u = (1, 0), v = (0, 1). Such a constraint is motivated by manufacturing and recycling, where materials must be cut or processed within width limits. For instance, Lan et al. [2… view at source ↗

**Figure 2.** Figure 2: (a) Vertical trapezoidal decomposition of P into V = {∆1, . . . , ∆6}, and decomposition of P into PL and PR by a vertical cut c of V . (b-c) Merging optimal strip partitions of PL and PR incident to c may or may not require an additional cut, depending on whether |I1 ∪ I2| ≤ 1 or > 1. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Let (EO, ⪯) be the antichain completion of (IO, ⊇). The figure illustrates the partial order, meet, and join operations for two antichains A, B ∈ EO: (a) A ⪯ B; (b) A ∧ B; (c) A ∨ B. Clarke–Cormack–Burkowski (CCB) lattice. A poset is a lattice if every pair of elements has a unique least upper bound (join) and a unique greatest lower bound (meet). For a locally finite, totally ordered set O, Boldi and Vign… view at source ↗

**Figure 4.** Figure 4: Subproblem structure (Q∆, e∆, ⃗η(e∆)) is defined for every non-root node ∆ of G = (V, E). 4.2 Subproblem structures in the refined dual tree We now describe the subproblem structure underlying our dynamic program for simple polygons, formulated in terms of antichains of intervals. We associate each subproblem with a pair (Q, e), where Q is a union of trapezoids from the vertical trapezoidal decomposition V… view at source ↗

**Figure 5.** Figure 5: (a) The trapezoid ∆ has three left children and two right children in the subtree G∆. (b) Refining the local star centered at ∆ into a binary tree. can be constructed in O(n) time. We refer to the original nodes of G as trapezoid nodes and the new internal nodes as bridge nodes. By construction, every trapezoid node in Ge has at most one child, and every bridge node has exactly two children. Subproblem str… view at source ↗

**Figure 6.** Figure 6: The subproblem structures (Qu, eu, ⃗η(eu)) in Ge when u is (a) a same-side bridge, (b) a cross-side bridge, and (c) the root; attaching the cap Tρ(ε) along eρ yields the simple polygon Qε ρ . inherited from the original dual tree G, where it is already well-defined. At the root node ρ, we have Qρ = P, the extended edge eρ has positive length, and ⃗η(eρ) is taken to be the outward normal of eρ with respect … view at source ↗

**Figure 7.** Figure 7: Additional vertical cuts are inserted when no strip can be merged or extended across the node: (a) trapezoid node, (b) same-side bridge node, and (c) cross-side bridge node. The update at a trapezoid node proceeds as follows. Let [a, b] be the x-interval of ∆, where a = x(ev) and b = x(eu). For each strip S ∈ Sε (Qv, ev), we remove the old cap Tv(ε), insert ∆ into the polygon, and then attach the new cap T… view at source ↗

**Figure 8.** Figure 8: Illustration of the reporting step for the example in [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗

**Figure 9.** Figure 9: (a) The construction of a simple polygon P = Q ∪ T ∪ Q′ . The staircase rectangles R1, . . . , Rn with their corridors form Q, and R′ with its corridor forms Q′ ; both attach to the rectangle T. (b) Determining whether opt(P) = n − 1 reduces to testing whether b lies within distance 1 4n of some ai , equivalently whether b ∈ [ai − 1 4n , ai + 1 4n ] for some i ∈ [n], where |ai − aj | > 1 4n for i ̸= j. Lem… view at source ↗

**Figure 10.** Figure 10: (a) A triangulated generalized terrain in R 3 whose projection onto the xy-plane defines a self-overlapping polygon. (b) An orthogonal strip partition of the corresponding self-overlapping polygon. (c) A counterexample represented by a (T, G)-model, but not a self-overlapping polygon. boundary C onto the x-axis. With these notions, the problem of orthogonal strip partitioning of self-overlapping polygons … view at source ↗

**Figure 11.** Figure 11: Encoding the input sequence x as a self-overlapping polygon P and its dual graph. (a) The rectangles RA i and RB i are attached to the left side of S by thin L-shaped pipes. (b) The refined binary tree Ge of the vertical trapezoidal decomposition of P, where the subtrees T A i and T B i correspond to RA i and RB i , respectively. exactly the intervals Ai and Bi , respectively. We arrange these rectangles … view at source ↗

read the original abstract

We study a variant of a polygon partition problem, introduced by Chung, Iwama, Liao, and Ahn [ISAAC'25]. Given orthogonal unit vectors $\mathbf{u},\mathbf{v}\in \mathbb{R}^2$ and a polygon $P$ with $n$ vertices, we partition $P$ into connected pieces by cuts parallel to $\mathbf{v}$ such that each resulting subpolygon has width at most one in direction $\mathbf{u}$. We consider the value version, which asks for the minimum number of strips, and the reporting version, which outputs a compact encoding of the cuts in an optimal strip partition. We give efficient algorithms and lower bounds for both versions on three classes of polygons of increasing generality: convex, simple, and self-overlapping. For convex polygons, we solve the value version in $O(\log n)$ time and the reporting version in $O\!\left(h \log\left(1 + \frac{n}{h}\right)\right)$ time, where $h$ is the width of $P$ in direction $\mathbf{u}$. We prove matching lower bounds in the decision-tree model, showing that the reporting algorithm is input-sensitive optimal with respect to $h$. For simple polygons, we present $O(n \log n)$-time, $O(n)$-space algorithms for both versions and prove an $\Omega(n)$ lower bound. For self-overlapping polygons, we extend the approach for simple polygons to obtain $O(n \log n)$-time, $O(n)$-space algorithms for both versions, and we prove a matching $\Omega(n \log n)$ lower bound in the algebraic computation-tree model via a reduction from the $\delta$-closeness problem. Our approach relies on a lattice-theoretic formulation of the problem. We represent strip partitions as antichains of intervals in the Clarke--Cormack--Burkowski lattice, originally developed for minimal-interval semantics in information retrieval. Within this lattice framework, we design a dynamic programming algorithm that uses the lattice operations of meet and join.

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.

Desk Editor's Note private letter to a colleague

The paper reduces orthogonal strip partitioning to antichain search in the Clarke-Cormack-Burkowski lattice and delivers matching upper and lower bounds for convex, simple, and self-overlapping polygons.

read the letter

The main takeaway is that this work turns the strip-partitioning task into a lattice problem and gets tight algorithms plus lower bounds for three polygon classes. For convex polygons the value version runs in O(log n) and the reporting version in O(h log(1 + n/h)), both with matching decision-tree lower bounds. Simple polygons get O(n log n) time and O(n) space with an Omega(n) lower bound. Self-overlapping polygons keep the O(n log n) bound but add an Omega(n log n) algebraic lower bound via reduction from delta-closeness. All of this rests on representing partitions as antichains and using meet and join for the minimum count. The lattice step is the genuinely new piece relative to the ISAAC'25 introduction of the problem, and the bounds line up without obvious slack. The reductions for the lower bounds are explicit rather than hand-wavy, which helps. The central modeling claim—that the lattice operations correctly encode the geometric width constraint—looks plausible from the abstract, but it is the part that needs the full proofs to confirm no edge cases slip through in the overlapping or non-convex settings. No free parameters or invented entities appear in the claims. This is for computational geometers who work on polygon decomposition or who might reuse lattice techniques on geometric data. A reader who needs concrete time bounds for strip problems in CAD or graphics will get direct value. The paper shows clear, grounded thinking and builds on the prior result without circularity, so it deserves a serious referee to check the lattice details and the self-overlapping extension. I would send it out for review.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's algorithms are derived via dynamic programming over antichains in the externally defined Clarke-Cormack-Burkowski lattice (originally from information retrieval), using standard meet/join operations to compute minimum strip partitions. Lower bounds follow from explicit reductions to known problems (decision-tree model for convex polygons; algebraic computation-tree reduction from delta-closeness for self-overlapping polygons). The citation to the problem's prior introduction [ISAAC'25] defines the input but does not supply the lattice model, DP recurrence, or complexity bounds. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citation chains appear in the derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the assumption that the Clarke-Cormack-Burkowski lattice correctly encodes the partial order of feasible strip cuts and that its meet/join operations preserve optimality for the minimum antichain cover.

axioms (1)

domain assumption The Clarke-Cormack-Burkowski lattice admits efficient meet and join operations that can be used inside dynamic programming to compute minimum antichains representing strip partitions.
Invoked when the abstract states that partitions are represented as antichains and solved via lattice DP.

pith-pipeline@v0.9.0 · 5675 in / 1280 out tokens · 36041 ms · 2026-05-10T08:31:01.443779+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references

[1]

Minimum star partitions of simple polygons in polynomial time

Mikkel Abrahamsen, Joakim Blikstad, André Nusser, and Hanwen Zhang. Minimum star partitions of simple polygons in polynomial time. InProc. 56th Annual ACM Symposium on Theory of Computing (STOC), pages 904–910. Association for Computing Machinery, 2024

2024
[2]

Partitioning a polygon into small pieces

Mikkel Abrahamsen and Nichlas Langhoff Rasmussen. Partitioning a polygon into small pieces. InProc. 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3562–3589. Society for Industrial and Applied Mathematics, 2025

2025
[3]

Hardness of packing, covering and partitioning simple polygons with unit squares

Mikkel Abrahamsen and Jack Stade. Hardness of packing, covering and partitioning simple polygons with unit squares. InProc. 65th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1355–1371. IEEE, 2024

2024
[4]

Cambridge University Press, 2009

Sanjeev Arora and Boaz Barak.Computational Complexity: A Modern Approach. Cambridge University Press, 2009. 31

2009
[5]

plank problem

Thøger Bang. A solution of the “plank problem”.Proc. American Mathematical Society, 2(6):990–993, 1951

1951
[6]

Bell, John G

Timothy C. Bell, John G. Cleary, and Ian H. Witten.Text Compression. Prentice-Hall, 1990

1990
[7]

Lower bounds for algebraic computation trees

Michael Ben-Or. Lower bounds for algebraic computation trees. InProc. 15th Annual ACM Symposium on Theory of Computing (STOC), pages 80–86. Association for Computing Machinery, 1983

1983
[8]

Efficient optimally lazy algorithms for minimal-interval semantics.Theoretical Computer Science, 648:8–25, 2016

Paolo Boldi and Sebastiano Vigna. Efficient optimally lazy algorithms for minimal-interval semantics.Theoretical Computer Science, 648:8–25, 2016

2016
[9]

On the lattice of antichains of finite intervals.Order, 35(1):57–81, 2018

Paolo Boldi and Sebastiano Vigna. On the lattice of antichains of finite intervals.Order, 35(1):57–81, 2018

2018
[10]

Chazelle and J

B. Chazelle and J. Incerpi. Triangulation and shape-complexity.ACM Transactions on Graphics, 3(2):135–152, 1984

1984
[11]

Triangulating a simple polygon in linear time.Discrete & Computational Geometry, 6(3):485–524, 1991

Bernard Chazelle. Triangulating a simple polygon in linear time.Discrete & Computational Geometry, 6(3):485–524, 1991

1991
[12]

Decomposing a polygon into its convex parts

Bernard Chazelle and David Dobkin. Decomposing a polygon into its convex parts. InProc. 11th Annual ACM Symposium on Theory of Computing (STOC), pages 38–48. Association for Computing Machinery, 1979

1979
[13]

Approxi- mating convex polygons by histogons

Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn. Approxi- mating convex polygons by histogons. InProc. 34th Canadian Conference on Computational Geometry (CCCG), 2022

2022
[14]

Minimum partition of polygons under width and cut constraints

Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn. Minimum partition of polygons under width and cut constraints. InProc. 36th International Symposium on Algorithms and Computation (ISAAC), pages 22:1–22:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025

2025
[15]

Charles L. A. Clarke, G. V. Cormack, and F. J. Burkowski. An algebra for structured text search and a framework for its implementation.The Computer Journal, 38(1):43–56, 1995

1995
[16]

Self-overlapping curves revisited

David Eppstein and Elena Mumford. Self-overlapping curves revisited. InProc. 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 160–169, 2009

2009
[17]

PhD thesis, University of California, Berkeley, 1996

Jeffrey Gordon Erickson.Lower Bounds for Fundamental Geometric Problems. PhD thesis, University of California, Berkeley, 1996

1996
[18]

Fournier and D

A. Fournier and D. Y. Montuno. Triangulating simple polygons and equivalent problems. ACM Transactions on Graphics, 3(2):153–174, 1984

1984
[19]

J. W. S. Hearle. The structural mechanics of fibers.Journal of Polymer Science Part C: Polymer Symposia, 20(1):215–251, 1967

1967
[20]

Selection from heaps, row-sorted matrices, and x+y using soft heaps

Haim Kaplan, László Kozma, Or Zamir, and Uri Zwick. Selection from heaps, row-sorted matrices, and x+y using soft heaps. InProc. 2nd Symposium on Simplicity in Algorithms (SOSA), pages 5:1–5:21. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2019. 32

2019
[21]

Mark Keil

J. Mark Keil. Decomposing a polygon into simpler components.SIAM Journal on Computing, 14(4):799–817, 1985

1985
[22]

Utilization of Waste Wind Turbine Blades in Performance Improvement of Asphalt Mixture.Frontiers in Materials, 10:1164693, 2023

Tianhui Lan, Bingze Wang, Junchao Zhang, Hao Wei, and Xu Liu. Utilization of Waste Wind Turbine Blades in Performance Improvement of Asphalt Mixture.Frontiers in Materials, 10:1164693, 2023

2023
[23]

Monotone partitions of simple polygons

Jaegun Lee, Hyojeong An, Hwi Kim, and Hee-Kap Ahn. Monotone partitions of simple polygons. InProc. 36th International Workshop on Combinatorial Algorithms (IWOCA), pages 72–85, 2025

2025
[24]

Lingas and V

A. Lingas and V. Soltan. Minimum convex partition of a polygon with holes by cuts in given directions.Theory of Computing Systems, 31(5):507–538, 1998

1998
[25]

PhD thesis, The University of Texas at Dallas, 1985

Robin Ru-Sheng Liu.Partitioning Rectilinear Polygons into Simpler Components. PhD thesis, The University of Texas at Dallas, 1985

1985
[26]

Lovász, Moni Naor, Ilan Newman, and Avi Wigderson

L. Lovász, Moni Naor, Ilan Newman, and Avi Wigderson. Search problems in the decision tree model.SIAM Journal on Discrete Mathematics, 8(1):119–132, 1995

1995
[27]

Preparata and Michael Ian Shamos.Computational Geometry

Franco P. Preparata and Michael Ian Shamos.Computational Geometry. Springer, 1985

1985
[28]

On the power of random access machines

Arnold Schönhage. On the power of random access machines. InProc. International Colloquium on Automata, Languages and Programming (ICALP), pages 520–529, 1979

1979
[29]

Shor and Christopher J

Peter W. Shor and Christopher J. Van Wyk. Detecting and decomposing self-overlapping curves.Computational Geometry, 2(1):31–50, 1992. 33

1992