4
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.