Maximum-Weight Two Boxes Symmetric Difference Problem
This provides a new algorithmic result for a specific geometric optimization problem, but it is incremental as it extends known techniques to a new variant.
The paper presents an O(n^4 log n) time algorithm to find two axis-aligned rectangles maximizing the total weight of points in their symmetric difference, and extends the framework to k boxes.
Let $P$ be a set of $n$ points in the plane, where each element of $P$ is assigned a weight $ω(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.