Maximum-Weight Two Boxes Symmetric Difference Problem

Carlos Seara; Jos\'e Fern\'andez Goycoolea; Luis H. Herrera; Pablo P\'erez Lantero

arxiv: 2605.22690 · v1 · pith:ZAE6H3W7new · submitted 2026-05-21 · 💻 cs.CG

Maximum-Weight Two Boxes Symmetric Difference Problem

Jos\'e Fern\'andez Goycoolea , Luis H. Herrera , Pablo P\'erez Lantero , Carlos Seara This is my paper

Pith reviewed 2026-05-22 03:27 UTC · model grok-4.3

classification 💻 cs.CG

keywords axis-aligned rectanglessymmetric differencemaximum weightcomputational geometrydynamic programmingalgorithm

0 comments

The pith

An O(n^4 log n) time algorithm finds two axis-aligned rectangles maximizing the weighted symmetric difference of points.

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

The paper develops an algorithm to choose two possibly overlapping axis-aligned rectangles that maximize the total weight of points lying in exactly one rectangle. This is useful when points have positive or negative weights because the symmetric difference lets negative-weight points be excluded while positive ones are included. The method runs in O(n^4 log n) time and linear space by restricting attention to a polynomial number of candidate rectangles whose sides are determined by the input points. The same approach adapts directly to versions with three or more rectangles or to maximizing weight in their union.

Core claim

We present an algorithm that runs in O(n^4 log n) time and O(n) space to find two possibly overlapping axis-aligned rectangles A and B so as to maximize the total weight of the points contained in the symmetric difference of A and B. The same optimization framework can easily be adapted to solve related problems such as to maximize the total weight in the symmetric difference of k ≥ 3 boxes and/or in the union of k ≥ 2 boxes.

What carries the argument

Candidate rectangles whose four sides each pass through at least one input point, combined with dynamic programming to evaluate combinations for the symmetric-difference objective.

If this is right

The identical candidate-enumeration technique yields an algorithm for the symmetric-difference problem with three or more boxes.
The same framework directly solves the maximum-weight union problem for two or more boxes.
Any geometric optimization problem whose optimum is attained at point-defined boundaries admits a comparable polynomial-time solution.

Where Pith is reading between the lines

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

The candidate-boundary idea may transfer to other set operations such as intersection or exclusive-or on rectangles.
Signed weights make the problem a natural model for coverage tasks that penalize over-coverage or noise.
Linear space usage suggests the algorithm can be implemented on large point sets without prohibitive memory.

Load-bearing premise

The optimal rectangles can always be chosen from the polynomial-sized family whose boundaries are fixed by the x- and y-coordinates of the input points.

What would settle it

A concrete point set whose maximum-weight symmetric difference is achieved only by rectangles whose sides miss every input-point coordinate.

Figures

Figures reproduced from arXiv: 2605.22690 by Carlos Seara, Jos\'e Fern\'andez Goycoolea, Luis H. Herrera, Pablo P\'erez Lantero.

**Figure 2.** Figure 2: (a) Containment intersection. (b) Corner intersection. (c) Cross intersection. (d) Side [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 2.** Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Figure 3: Optimization framework example. When the lines ℓi are fixed, the optimization problem is 1-dimensional and can be solved recursively in O(n) time through the construction of the generalized MCS-tree data structure that is described in the next section. If the generalized MCS-tree is already constructed then, it can be updated to reflect a change in the cost of a single point in O(log n) time. The algorithm… view at source ↗

**Figure 4.** Figure 4: Recursive computation cases of M(U) (top) and R2(U) (down). Hence, the solution to the 1-dimensional problem for fixed lines is M(X); stored at the root of the tree. The complete set of values is A(U) = {Ss,e(U), Ls(U), M(U), Re(U) | for all 1 ≤ s ≤ e ≤ 3}, which now has 13 numbers that are defined similarly to M(U) but with restrictions on which functions fj are summed and requirements on the inclusion of… view at source ↗

read the original abstract

Let $P$ be a set of $n$ points in the plane, where each element of $P$ is assigned a weight $\omega(p)$, positive or negative. In this paper, we present an algorithm that runs in $O(n^4\log n)$ time and $O(n)$ space to find two possibly overlapping axis-aligned rectangles $A$ and $B$ so as to maximize the total weight of the points contained in the symmetric difference of $A$ and $B$. The same optimization framework can easily be adapted to solve related problems such as to maximize the total weight in the symmetric difference of $k \geq 3$ boxes and/or in the union of $k \geq 2$ boxes.

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 claims an O(n^4 log n) algorithm for two axis-aligned boxes maximizing signed-weight symmetric difference, but the reduction from O(n^8) pairs is the part that needs the full details to hold up.

read the letter

The main point is a polynomial algorithm that picks two possibly overlapping axis-aligned rectangles to maximize the sum of point weights in their symmetric difference, allowing negative weights, with an O(n^4 log n) time and O(n) space bound. The same setup is said to extend to k boxes or to union instead of symmetric difference. This formulation is the actual novelty here. Prior geometric optimization work usually targets union or intersection; symmetric difference subtracts the overlap exactly once, and negative weights can make overlap costly rather than neutral or beneficial. That shift creates a different set of candidate optima. The linear space claim is also practical if the method avoids heavy auxiliary structures. The time bound is where the work is thinnest on the surface. There are O(n^4) rectangles whose sides pass through input points, so O(n^8) pairs in the obvious enumeration. Reaching O(n^4 log n) therefore requires either a sweep, dynamic programming over sorted coordinates, or a data structure that finds the best partner rectangle without checking every combination while still guaranteeing the global maximum. The symmetric-difference weight calculation must correctly subtract the intersection region even when negative-weight points sit inside it; any shortcut that ignores boundary cases there could miss the true optimum. The abstract states the result but does not show the candidate reduction or the correctness argument, so the stress-test concern about an implicit non-obvious compression of the search space is fair until the full proof is checked. This is for computational geometry researchers who work on range queries or box selection with custom objectives. Someone extending union-based results to signed or overlap-penalized versions would find the framework useful. It deserves peer review because the claim is specific, the space bound is attractive, and the extension remarks suggest follow-up potential even if the central reduction needs careful verification.

Referee Report

2 major / 1 minor

Summary. The paper claims an O(n^4 log n)-time, O(n)-space algorithm that, given n weighted points in the plane, returns two axis-aligned rectangles A and B maximizing the total weight of points lying in the symmetric difference A Δ B. The same framework is stated to extend to maximizing the symmetric difference of k ≥ 3 boxes or the union of k ≥ 2 boxes.

Significance. If the stated time bound is achieved while guaranteeing optimality, the result would constitute a non-trivial improvement over the naïve O(n^8) enumeration of all pairs of point-defined rectangles. The O(n) space bound is also noteworthy. The claimed extensibility to k-box variants suggests the underlying technique may be reusable, but the significance hinges on whether the reduction from O(n^8) candidate pairs to an O(n^4 log n) search is both correct and fully justified.

major comments (2)

Abstract: the central claim is an O(n^4 log n) algorithm, yet no derivation, candidate-enumeration strategy, or correctness argument is supplied. Because two independent point-defined rectangles generate Θ(n^8) pairs and the symmetric-difference objective requires exact subtraction of the intersection weight, the manuscript must explicitly show how the search space is reduced to O(n^4) configurations (via sweeping, DP on sorted coordinates, or a data structure) while still considering the global optimum; without this argument the time bound cannot be verified.
The weakest assumption noted in the review—that a polynomial number of candidate rectangles suffice—is load-bearing. The paper should contain a lemma (or section) proving that every optimal rectangle can be assumed to have its four sides passing through input points, and that the optimal pair can be found by optimizing over a polynomially smaller set of joint configurations; if this lemma is missing or only sketched, the O(n^4 log n) claim rests on an unproven reduction.

minor comments (1)

Abstract: the phrase “can easily be adapted” for the k-box cases should be accompanied by at least a one-paragraph outline of the necessary modifications, even if the full details are deferred to a future paper.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and insightful comments on our manuscript. We address the major comments point by point below, and we plan to incorporate revisions to enhance the clarity of our algorithmic description and proofs.

read point-by-point responses

Referee: Abstract: the central claim is an O(n^4 log n) algorithm, yet no derivation, candidate-enumeration strategy, or correctness argument is supplied. Because two independent point-defined rectangles generate Θ(n^8) pairs and the symmetric-difference objective requires exact subtraction of the intersection weight, the manuscript must explicitly show how the search space is reduced to O(n^4) configurations (via sweeping, DP on sorted coordinates, or a data structure) while still considering the global optimum; without this argument the time bound cannot be verified.

Authors: We agree that the abstract, being a concise summary, does not include the full technical derivation. The manuscript provides the candidate-enumeration strategy and correctness argument in the main body, specifically through a combination of coordinate compression, sweeping, and dynamic programming as detailed in Sections 3 and 4. To improve accessibility, we will revise the introduction to include a brief overview of how the O(n^4 log n) bound is achieved by reducing the naive enumeration of rectangle pairs. revision: yes
Referee: The weakest assumption noted in the review—that a polynomial number of candidate rectangles suffice—is load-bearing. The paper should contain a lemma (or section) proving that every optimal rectangle can be assumed to have its four sides passing through input points, and that the optimal pair can be found by optimizing over a polynomially smaller set of joint configurations; if this lemma is missing or only sketched, the O(n^4 log n) claim rests on an unproven reduction.

Authors: We acknowledge the importance of explicitly stating this assumption. While the manuscript assumes standard properties of optimal axis-aligned rectangles (that their boundaries can be aligned with input points without loss of optimality), we will add a formal lemma in Section 2 that proves every optimal rectangle has sides passing through points and extends this to pairs for the symmetric difference objective. This will include a proof that the global optimum is achieved within the polynomially bounded set of configurations considered by our algorithm. revision: yes

Circularity Check

0 steps flagged

No circularity: direct algorithmic construction with explicit candidate enumeration.

full rationale

The paper states an O(n^4 log n) algorithm for maximizing symmetric-difference weight over two axis-aligned rectangles. Candidate rectangles are formed by choosing boundaries from the n input points (O(n^4) single rectangles), and the algorithm uses sweeping or dynamic programming to search pairs while correctly handling the intersection subtraction for the symmetric difference. No equations reduce a claimed prediction to a fitted parameter, no self-citation is load-bearing for the core result, and the derivation is self-contained as a standard geometric optimization procedure. The O(n^8) naive pair count is reduced by coordinate sorting and data structures without assuming the optimum in advance.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; the contribution rests on standard assumptions of the real RAM model in computational geometry.

pith-pipeline@v0.9.0 · 5661 in / 1047 out tokens · 49975 ms · 2026-05-22T03:27:49.334004+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · 2 internal anchors

[1]

E. M. Arkin, G. Barequet, and J. S. B. Mitchell. Algorithms for two-box covering. InProceedings of the twenty-second Annual Symposium on Computational Geometry, pages 459–467, 2006. 9

work page 2006
[2]

Maximum-width Axis-Parallel Empty Rectangular Annulus

A. Baral, A. Gondane, S. Sadhu, and P. R. S. Mahapatra. Maximum-width axis-parallel empty rectangular annulus.arXiv preprint arXiv:1712.00375, 2017

work page internal anchor Pith review Pith/arXiv arXiv 2017
[3]

Barbay, T

J. Barbay, T. M. Chan, G. Navarro, and P. P´ erez-Lantero. Maximum-weight planar boxes inO(n 2) time (and better).Information Processing Letters, 114(8):437–445, 2014

work page 2014
[4]

Adaptive Techniques to find Optimal Planar Boxes

J. Barbay, G. Navarro, and P. P´ erez-Lantero. Adaptive techniques to find optimal planar boxes. CoRR, abs/1204.2034, 2012

work page internal anchor Pith review Pith/arXiv arXiv 2034
[5]

Bautista-Santiago, J

C. Bautista-Santiago, J. D´ ıaz-B´ a˜ nez, D. Lara, P. P´ erez-Lantero, J. Urrutia, and I. Ventura. Computing optimal islands.Operations Research Letters, 39(4):246–251, 2011

work page 2011
[6]

Becker, P

B. Becker, P. G. Franciosa, S. Gschwind, S. Leonardi, T. Ohler, and P. Widmayer. Enclosing a set of objects by two minimum area rectangles.Journal of Algorithms, 21(3):520–541, 1996

work page 1996
[7]

Bereg, J

S. Bereg, J. D´ ıaz-B´ a˜ nez, D. Lara, P. P´ erez-Lantero, C. Seara, and J. Urrutia. On the coarseness of bicolored point sets.Computational Geometry, 46(1):65–77, 2013

work page 2013
[8]

Bespamyatnikh and M

S. Bespamyatnikh and M. Segal. Covering a set of points by two axis-parallel boxes.Information Processing Letters, 75(3):95–100, 2000

work page 2000
[9]

Cabello, J

S. Cabello, J. D´ ıaz-B´ a˜ nez, and P. P´ erez-Lantero. Covering a bichromatic point set with two disjoint monochromatic disks.Computational Geometry, 46(3):203–212, 2013

work page 2013
[10]

Cabello, J

S. Cabello, J. M. D´ ıaz-B´ a˜ nez, C. Seara, J. A. Sellar` es, J. Urrutia, and I. Ventura. Covering point sets with two disjoint disks or squares.Computational Geometry, 40(3):195–206, 2008

work page 2008
[11]

L. E. Caraballo, C. Ochoa, P. P´ erez-Lantero, and J. Rojas-Ledesma. Matching colored points with rectangles.Journal of Combinatorial Optimization, 33(2):403–421, 2017

work page 2017
[12]

Chazelle and D

B. Chazelle and D. Lee. On a circle placement problem.Computing, 36:1–16, 03 1986

work page 1986
[13]

Cort´ es, J

C. Cort´ es, J. M. D´ ıaz-B´ a˜ nez, P. P´ erez-Lantero, C. Seara, J. Urrutia, and I. Ventura. Bichromatic separability with two boxes: A general approach.J. Algorithms, 64(2-3):79–88, 2009

work page 2009
[14]

D. P. Dobkin, D. Gunopulos, and W. Maass. Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning.Journal of Computer and System Sciences, 52(3):453–470, 1996

work page 1996
[15]

D´ ıaz-B´ a˜ nez, R

J. D´ ıaz-B´ a˜ nez, R. Fabila-Monroy, P. P´ erez-Lantero, and I. Ventura. New results on the coarseness of bicolored point sets.Information Processing Letters, 123:1–7, 2017

work page 2017
[16]

D´ ıaz-B´ a˜ nez, M

J. D´ ıaz-B´ a˜ nez, M. Lopez, C. Ochoa, and P. P´ erez-Lantero. Computing the coarseness with strips or boxes.Discrete Applied Mathematics, 224:80–90, 2017

work page 2017
[17]

Eckstein, P

J. Eckstein, P. L. Hammer, Y. Liu, M. Nediak, and B. Simeone. The maximum box problem and its application to data analysis.Comput. Optim. Appl., 23(3):285–298, Dec. 2002

work page 2002
[18]

Fern´ andez Goycoolea, L

J. Fern´ andez Goycoolea, L. H. Herrera, P. P´ erez-Lantero, and C. Seara. Computing the coarseness measure of a bicolored point set over guillotine partitions.Results in Applied Mathematics, 24:100503, 2024

work page 2024
[19]

Gonz´ alez-Aguilar, D

H. Gonz´ alez-Aguilar, D. Orden, P. P´ erez-Lantero, D. Rappaport, C. Seara, J. Tejel, and J. Urrutia. Maximum rectilinear convex subsets.SIAM Journal on Computing, 50(1):145–170, 2021. 10

work page 2021

[1] [1]

E. M. Arkin, G. Barequet, and J. S. B. Mitchell. Algorithms for two-box covering. InProceedings of the twenty-second Annual Symposium on Computational Geometry, pages 459–467, 2006. 9

work page 2006

[2] [2]

Maximum-width Axis-Parallel Empty Rectangular Annulus

A. Baral, A. Gondane, S. Sadhu, and P. R. S. Mahapatra. Maximum-width axis-parallel empty rectangular annulus.arXiv preprint arXiv:1712.00375, 2017

work page internal anchor Pith review Pith/arXiv arXiv 2017

[3] [3]

Barbay, T

J. Barbay, T. M. Chan, G. Navarro, and P. P´ erez-Lantero. Maximum-weight planar boxes inO(n 2) time (and better).Information Processing Letters, 114(8):437–445, 2014

work page 2014

[4] [4]

Adaptive Techniques to find Optimal Planar Boxes

J. Barbay, G. Navarro, and P. P´ erez-Lantero. Adaptive techniques to find optimal planar boxes. CoRR, abs/1204.2034, 2012

work page internal anchor Pith review Pith/arXiv arXiv 2034

[5] [5]

Bautista-Santiago, J

C. Bautista-Santiago, J. D´ ıaz-B´ a˜ nez, D. Lara, P. P´ erez-Lantero, J. Urrutia, and I. Ventura. Computing optimal islands.Operations Research Letters, 39(4):246–251, 2011

work page 2011

[6] [6]

Becker, P

B. Becker, P. G. Franciosa, S. Gschwind, S. Leonardi, T. Ohler, and P. Widmayer. Enclosing a set of objects by two minimum area rectangles.Journal of Algorithms, 21(3):520–541, 1996

work page 1996

[7] [7]

Bereg, J

S. Bereg, J. D´ ıaz-B´ a˜ nez, D. Lara, P. P´ erez-Lantero, C. Seara, and J. Urrutia. On the coarseness of bicolored point sets.Computational Geometry, 46(1):65–77, 2013

work page 2013

[8] [8]

Bespamyatnikh and M

S. Bespamyatnikh and M. Segal. Covering a set of points by two axis-parallel boxes.Information Processing Letters, 75(3):95–100, 2000

work page 2000

[9] [9]

Cabello, J

S. Cabello, J. D´ ıaz-B´ a˜ nez, and P. P´ erez-Lantero. Covering a bichromatic point set with two disjoint monochromatic disks.Computational Geometry, 46(3):203–212, 2013

work page 2013

[10] [10]

Cabello, J

S. Cabello, J. M. D´ ıaz-B´ a˜ nez, C. Seara, J. A. Sellar` es, J. Urrutia, and I. Ventura. Covering point sets with two disjoint disks or squares.Computational Geometry, 40(3):195–206, 2008

work page 2008

[11] [11]

L. E. Caraballo, C. Ochoa, P. P´ erez-Lantero, and J. Rojas-Ledesma. Matching colored points with rectangles.Journal of Combinatorial Optimization, 33(2):403–421, 2017

work page 2017

[12] [12]

Chazelle and D

B. Chazelle and D. Lee. On a circle placement problem.Computing, 36:1–16, 03 1986

work page 1986

[13] [13]

Cort´ es, J

C. Cort´ es, J. M. D´ ıaz-B´ a˜ nez, P. P´ erez-Lantero, C. Seara, J. Urrutia, and I. Ventura. Bichromatic separability with two boxes: A general approach.J. Algorithms, 64(2-3):79–88, 2009

work page 2009

[14] [14]

D. P. Dobkin, D. Gunopulos, and W. Maass. Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning.Journal of Computer and System Sciences, 52(3):453–470, 1996

work page 1996

[15] [15]

D´ ıaz-B´ a˜ nez, R

J. D´ ıaz-B´ a˜ nez, R. Fabila-Monroy, P. P´ erez-Lantero, and I. Ventura. New results on the coarseness of bicolored point sets.Information Processing Letters, 123:1–7, 2017

work page 2017

[16] [16]

D´ ıaz-B´ a˜ nez, M

J. D´ ıaz-B´ a˜ nez, M. Lopez, C. Ochoa, and P. P´ erez-Lantero. Computing the coarseness with strips or boxes.Discrete Applied Mathematics, 224:80–90, 2017

work page 2017

[17] [17]

Eckstein, P

J. Eckstein, P. L. Hammer, Y. Liu, M. Nediak, and B. Simeone. The maximum box problem and its application to data analysis.Comput. Optim. Appl., 23(3):285–298, Dec. 2002

work page 2002

[18] [18]

Fern´ andez Goycoolea, L

J. Fern´ andez Goycoolea, L. H. Herrera, P. P´ erez-Lantero, and C. Seara. Computing the coarseness measure of a bicolored point set over guillotine partitions.Results in Applied Mathematics, 24:100503, 2024

work page 2024

[19] [19]

Gonz´ alez-Aguilar, D

H. Gonz´ alez-Aguilar, D. Orden, P. P´ erez-Lantero, D. Rappaport, C. Seara, J. Tejel, and J. Urrutia. Maximum rectilinear convex subsets.SIAM Journal on Computing, 50(1):145–170, 2021. 10

work page 2021