Maximum-Weight Two Boxes Symmetric Difference Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918516676886528 |
|---|---|
| author | Goycoolea, José Fernández Herrera, Luis H. Lantero, Pablo Pérez Seara, Carlos |
| author_facet | Goycoolea, José Fernández Herrera, Luis H. Lantero, Pablo Pérez Seara, Carlos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_22690 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maximum-Weight Two Boxes Symmetric Difference Problem Goycoolea, José Fernández Herrera, Luis H. Lantero, Pablo Pérez Seara, Carlos Computational Geometry 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. |
| title | Maximum-Weight Two Boxes Symmetric Difference Problem |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2605.22690 |