<p>This seems like a hard problem. You might be able to do something if the rectangles have some packing property. For example, if no point is covered more than $t$ times (for some constant T), and the rectangles are not too long and narrow. Then one can probably prove that a curve intersects $O( \sqrt{n})$ rectangles, using some $k$-ply planar separator argument. </p>

CC BY-SA 3.0
2013-03-08T04:15:18.183Z
2013-03-08T04:15:18.183Z
Sariel Har-Peled
<p>Fix a constant $0&lt;\alpha&lt;1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the range $[0,M]$ for some $M$. Let $W=\sum w_i$. Find a simple (i.e. non self-intersecting) curve that partitions them into two sets of rectangles such that each set has total weight at least $\alpha W$ and the total weight of all rectangles cut by the curve is as small as possible, or output that no such curve exists. This is NP-complete, and I'm interested in a good heuristic/approximation algorithms with $O(N+poly(M))$ time (or more exactly $O(N+poly(M)+polylog(W))$ time).</p>

<p>A thorough search doesn't give me any reference in literature that studies this problem. Any insight is appreciated!</p>

<cg.comp-geom><heuristics><convex-geometry>
Balanced partitioning of a set of axis-parallel 2D rectangles
T. Huynh
# Balanced partitioning of a set of axis-parallel 2D rectangles

(Asked by: username_0 on 2013-03-06)

Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w\_1, w\_2,\ldots, w\_N$ and with coordinates all in the range $[0,M]$ for some $M$. Let $W=\sum w\_i$. Find a simple (i.e. non self-intersecting) curve that partitions them into two sets of rectangles such that each set has total weight at least $\alpha W$ and the total weight of all rectangles cut by the curve is as small as possible, or output that no such curve exists. This is NP-complete, and I'm interested in a good heuristic/approximation algorithms with $O(N+poly(M))$ time (or more exactly $O(N+poly(M)+polylog(W))$ time).

A thorough search doesn't give me any reference in literature that studies this problem. Any insight is appreciated!

**Tags:** cg.comp-geom, heuristics, convex-geometry


---

## 1 answers

### Answer by username_1 on 2013-03-08. Score: 4

This seems like a hard problem. You might be able to do something if the rectangles have some packing property. For example, if no point is covered more than $t$ times (for some constant T), and the rectangles are not too long and narrow. Then one can probably prove that a curve intersects $O( \sqrt{n})$ rectangles, using some $k$-ply planar separator argument.


---

