pith. sign in

arxiv: 1906.11948 · v1 · pith:CEPNKXLHnew · submitted 2019-06-27 · 💻 cs.CG

Packing Boundary-Anchored Rectangles and Squares

Therese Biedl , Ahmad Biniaz , Anil Maheshwari , Saeed Mehrabi This is my paper

Pith reviewed 2026-05-25 13:29 UTC · model grok-4.3

classification 💻 cs.CG
keywords boundary-anchored packingrectanglessquareslinear timeaxis-alignedcomputational geometrymaximum area
0
0 comments X

The pith

A linear-time algorithm finds the maximum total area for packing boundary-anchored rectangles inside a square when points are pre-sorted.

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

The authors study how to select a maximum-area set of interior-disjoint axis-aligned rectangles inside a square, where each rectangle is anchored at one of n given points on the boundary and each point anchors at most one rectangle. They provide a linear-time solution for this optimization when the points arrive already ordered along the boundary. A sympathetic reader would care because the result turns an apparently combinatorial packing task into a fast, practical computation for large inputs. The paper also supplies a quartic-time method for the variant that uses squares rather than rectangles when all anchor points lie on two opposite sides.

Core claim

We show how to solve this problem in time linear in n, provided that the points of P are given in sorted order along the boundary of Q. We also consider the problem for anchoring squares and give an O(n^4)-time algorithm when the points in P lie on two opposite sides of Q.

What carries the argument

The linear-time algorithm that processes the boundary points in sorted order to select and place the anchored rectangles.

If this is right

  • The maximum-area packing of anchored rectangles is computable in linear time under the sorted-input precondition.
  • The same framework yields an O(n^4) solution for anchored squares restricted to opposite sides.
  • Each point on the boundary can be used to anchor at most one rectangle or square in the optimal solution.
  • The rectangles remain interior-disjoint and axis-aligned throughout the packing.

Where Pith is reading between the lines

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

  • If sorting the points is the only extra cost, the overall problem remains efficient for moderate n.
  • The method may generalize to other convex shapes with a clear boundary ordering.
  • Applications requiring repeated packing queries could pre-sort the boundary once and then solve quickly.

Load-bearing premise

The points of P are already provided in sorted order along the boundary of the square.

What would settle it

An instance of sorted points on the square boundary for which the linear-time procedure returns a packing whose total area is strictly less than some other valid packing.

Figures

Figures reproduced from arXiv: 1906.11948 by Ahmad Biniaz, Anil Maheshwari, Saeed Mehrabi, Therese Biedl.

Figure 1
Figure 1. Figure 1: Instances and (non-optimal) solutions of (a) the ARP problem, and (b) the BARP [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: BARP can be solved via maximum-weight independent set in an outer-string graph. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a) The grid Γ. (b) White regions are holes. Graph G(S) is in red (thick); filled vertices are points of P. The max-segment s1 is introduced while s2 is not. (i) there exists a point p1 ∈ P on a corner of Q, or (ii) there exist two points p1, p2 ∈ PL ∪ PR that have the same y-coordinates, or (iii) there exist two points p1, p2 ∈ PT ∪ PB that have the same x-coordinates. Then we can cover all of Q with anch… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the proof of Lemma 3.1. indeed can be shortened/lengthened, because none of them can be anchored at a point on s: the only points of s that are possibly in P are its ends, but neither of them anchors a rectangle since s is not introduced. If this move of s increases the coverage, then S was not optimal, a contradiction. If this decreases the coverage, then moving downward in parallel would … view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the proof of Lemma 3.2. We know that r1 6= r c since r1 was anchored on the left side of Q. This contradicts that S has the minimum number of rectangles, so r c has cP as its top-left corner. If the right side rs(r1) of r1 is a sub-segment of bc, then we can stretch r1 to the right to increase the coverage of S, contradicting optimality. So rs(r1) must be a strict super-segment of bc, which… view at source ↗
Figure 6
Figure 6. Figure 6: With a guillotine cut, a hole can be found in [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Any rectangle whose boundary is directed suitably can be realized as hole. [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: If a hole that satisfies the hole-condition is bisected by a line [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: (a) The grid lines for every point p. (b) An optimal solution in which the square anchored at w is not introduced by Γ. obtain a grid as follows. For every point p on the bottom side of Q we add the following lines to the grid (see [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: (a) The construction of S (b) Illustration of the proof of Lemma 4.1. As a consequence of Lemma 4.1, to solve the BASP problem, it suffices to find a subset of non-overlapping squares in S with maximum area. For every square s ∈ S, we introduce a closed interval Is with the bottom side of s. We set the weight of Is to be the area of s. Let I be the set of these intervals. Any maximum-weight independent se… view at source ↗
Figure 11
Figure 11. Figure 11: (a) The lines that are added to L for p. (b) Illustration of the proof of Lemma 4.3. (1) y = px; this line represents the top side of the largest square that has p on its bottom-right corner. (2) y = 1 − px; this line represents the top side of the largest square that has p on its bottom-left corner. (3) for every point q 6= p on the bottom side of Q, we add y = |px − qx|; this line represents the top sid… view at source ↗
read the original abstract

Consider a set $P$ of $n$ points on the boundary of an axis-aligned square $Q$. We study the boundary-anchored packing problem on $P$ in which the goal is to find a set of interior-disjoint axis-aligned rectangles in $Q$ such that each rectangle is anchored (has a corner at some point in $P$), each point in $P$ is used to anchor at most one rectangle, and the total area of the rectangles is maximized. Here, a rectangle is anchored at a point $p$ in $P$ if one of its corners coincides with $p$. In this paper, we show how to solve this problem in time linear in $n$, provided that the points of $P$ are given in sorted order along the boundary of $Q$. We also consider the problem for anchoring squares and give an $O(n^4)$-time algorithm when the points in $P$ lie on two opposite sides of $Q$.

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

0 major / 1 minor

Summary. The paper claims an O(n)-time algorithm for maximizing the total area of interior-disjoint axis-aligned rectangles anchored at n boundary points of a square Q, when the points are supplied already sorted along the boundary; it also claims an O(n^4)-time algorithm for the analogous problem in which the anchored shapes are squares and the points lie on two opposite sides of Q.

Significance. If the stated algorithms and their analyses are correct, the linear-time rectangle result is notable for achieving optimal time under an explicitly stated input precondition. The explicit precondition on sorted order is a strength that removes ambiguity about input representation. No machine-checked proofs or parameter-free derivations are present, but the direct algorithmic construction for a geometric packing problem constitutes a concrete contribution.

minor comments (1)
  1. Abstract: the claim that the points are 'given in sorted order' is load-bearing for the linear-time result; a single sentence indicating the high-level technique (e.g., dynamic programming along the boundary or greedy sweep) would make the abstract self-contained without lengthening it appreciably.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the paper, for highlighting the strength of the explicit sorted-input precondition, and for recommending minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; direct algorithmic construction

full rationale

The paper claims an O(n) algorithm for maximum-area boundary-anchored rectangle packing (and O(n^4) for squares) when input points are explicitly preconditioned to be sorted along the boundary. This is a standard algorithmic result with no equations, fitted parameters, predictions of derived quantities, or self-citations invoked as load-bearing premises. The central claim reduces to a constructive algorithm whose correctness does not depend on re-deriving its own inputs or renaming prior results. No patterns from the enumerated circularity kinds apply.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no mathematical derivations, parameters, or background assumptions beyond the problem definition itself.

pith-pipeline@v0.9.0 · 5703 in / 1006 out tokens · 23034 ms · 2026-05-25T13:29:57.855531+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

10 extracted references · 10 canonical work pages

  1. [1]

    Kevin Balas, Adrian Dumitrescu, and Csaba D. Tóth. Anchored rectangle and square packings. In proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), Boston, MA, USA, pages 13:1–13:16, 2016. 1, 2, 3, 5, 17

    work page 2016

  2. [2]

    Kevin Balas and Csaba D. Tóth. On the number of anchored rectangle packings for a planar point set. Theor. Comput. Sci., 654:143–154, 2016. 2

    work page 2016

  3. [3]

    Biedl, Ahmad Biniaz, Anil Maheshwari, and Saeed Mehrabi

    Therese C. Biedl, Ahmad Biniaz, Anil Maheshwari, and Saeed Mehrabi. Packing boundary- anchored rectangles. Inproceedings of the 29th Canadian Conference on Computational Geom- etry (CCCG 2016), Ottawa, Canada, 2017. 1

    work page 2016

  4. [4]

    Adrian Dumitrescu and Csaba D. Tóth. Packing anchored rectangles.Combinatorica, 35(1):39– 61, 2015. 2

    work page 2015

  5. [5]

    An efficient algorithm for finding a maximum weight 2-independent set on interval graphs.Inform

    Ju Yuan Hsiao, Chuan Yi Tang, and Ruay Shiung Chang. An efficient algorithm for finding a maximum weight 2-independent set on interval graphs.Inform. Process. Lett., 43(5):229–235,

    work page

  6. [6]

    Elasticlabelsaroundtheperimeterofamap

    ClaudiaIturriagaandAnnaLubiw. Elasticlabelsaroundtheperimeterofamap. J. Algorithms, 47(1):14–39, 2003. 2

    work page 2003

  7. [7]

    Kakoulis and Ioannis G

    Konstantinos G. Kakoulis and Ioannis G. Tollis. Labeling algorithms. In Roberto Tamassia, ed- itor, Handbook on Graph Drawing and Visualization., pages 489–515. Chapman and Hall/CRC,

    work page

  8. [8]

    Mark Keil, Joseph S

    J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, and Martin Vatshelle. An algorithm for the maximum weight independent set problem on outerstring graphs. Comput. Geom., 60:19–25, 2017. 3

    work page 2017

  9. [9]

    W. Tutte. Recent progress in combinatorics. Inproceedings of the 3rd Waterloo Conference on Combinatorics, 1968. 2

    work page 1968

  10. [10]

    van Kreveld, Tycho Strijk, and Alexander Wolff

    Marc J. van Kreveld, Tycho Strijk, and Alexander Wolff. Point labeling with sliding labels. Comput. Geom., 13(1):21–47, 1999. 2 18

    work page 1999