$\new­com­mand{\R}{\mathbb{R}}\De­clar­e­Math­Op­er­a­tor{\E}{\mathbf{E}}\De­clar­e­Math­Op­er­a­tor{\deg}{deg}$

Here are my orig­i­nal hand­writ­ten notes on this topic.

This prob­lem is also known as Max­i­mum In­de­pen­dent Set in Unit Height Rec­tan­gles

• Input: A set $S$ of $n$ axis-aligned rec­tan­gles, all of which have height 1.
• Out­put: A sub­set of $I\sub­seteq S$ of pair­wise-dis­joint rec­tan­gles hav­ing max­i­mum car­di­nal­ity.

This mod­els a map la­belling prob­lem where we have $n$ place la­bels at spe­cific lo­ca­tions on a map, but we don't want two la­bels to over­lap. All the la­bels have the same height be­cause they're all writ­ten in the same font.

A $\frac{1}{2}$-Ap­prox­i­ma­tion

Here is an al­go­rithm that gives a 2-ap­prox­i­ma­tion:

1. Draw a set of hor­i­zon­tal lines $L_1,\ldots,L_k$ such that:
   1. The dis­tance be­tween any two lines is at least 1
   2. Each line in­ter­sects at least one rec­tan­gle in $S$
   3. Each rec­tan­gle in $R$ in­ter­sects at least one line
2. Let $S_i$ be the sub­set of $S$ that in­ter­sects $L_i$, and find a MIS, $I_i$, of $S_i$, for each $i\in\{1,\ldots,k\}$.
3. Out­put $I_1\cup I_3\cup I_5\cup\cdots,\cup I_{2\lceil k/2\rceil-1}$ or $I_2\cup I_4\cup I_6\cup\cdots,\cup I_{2\lfloor k/2\rfloor}$, whichever is big­ger.

We still don't know how to per­form Step 2 ef­fi­ciently, but let's ig­nore that for now. First, we can be sure that the al­go­rithm out­puts an in­de­pen­dent set be­cause each $I_i$ is an in­de­pen­dent set and the rec­tan­gles in $I_i$ can not in­ter­sect the rec­tan­gles in $I_{i+2j}$ be­cause the dis­tance be­tween $L_i$ and $L_{i+2j}$ is at least $2j\ge 2$.

Next, let's con­vince our­selves that this is a 2-ap­prox­i­ma­tion. Con­sider some op­ti­mal so­lu­tion $I^\star$. We can par­ti­tion $I^\star$ into $k$ sets $I^\star_1,\ldots,I^star_k$ where $I^\star_i=I^\star\cap S_i$, for each $i\in\{1,\ldots,k\}$. So \[ |I^\star| = \sum_{i=1}^k |I^\star_i| \le \sum_{i=1}^k |I_i| \en­space , \] where the sec­ond in­equal­ity comes from the fact that $I_i$ is a max­i­mum in­de­pen­dent set of $S_i$ while $I^\star_i$ is an in­de­pen­dent set of $S_i$. But now we're done, be­cause the so­lu­tion out­put by our ap­prox­i­ma­tion al­go­rithm has size at least \[ \frac{1}{2}\sum_{i=1}^k |I_i| \ge \frac{1}{2}|I^\star| \en­space . \] So, the only thing left to ex­plain is how to im­ple­ment Step 2, find­ing an MIS of $S_i$.

Find­ing an MIS in an In­ter­val graph

Each set $S_i$ is a set of axis-aligned rec­tan­gles that are all stabbed by the hor­i­zon­tal line $L_i$. A few sec­onds of re­flec­tion will con­vince you that this means we can for­get about the rec­tan­gles and just focus on their in­ter­sec­tions with $L_i$. This means we have to solve the fol­low­ing sim­pler prob­lem:

• Input: A set $T=\{[a_1,b_1],[a_2,b_2],\ldots,[a_n,b_n]\}$ of $n$ real in­ter­vals.
• Out­put: A sub­set of $I\sub­seteq S$ of pair­wise-dis­joint in­ter­vals hav­ing max­i­mum car­di­nal­ity.

It turns out that this can be solved op­ti­mally by a greedy al­go­rithm:

1. Sort $T$ by the right end­point of each in­ter­val so that $b_1\le b_2\le b_3\le\cdots\le b_n$.
2. $I\gets\emp­ty­set$
3. for each $i\in\{1,\ldots,n\}$ do
   1. if $[a_i,b_i]\in T$
      1. $I\gets I\cup\{[a_i,b_i]\}$.
      2. re­move every in­ter­val in $T$ that in­ter­sects $[a_i,b_i]$
4. re­turn $I$

We can prove that this al­go­rithm is op­ti­mal by in­duc­tion on $n$. The case $n=0$ is triv­ial. Let $I^\star$ be some op­ti­mal so­lu­tion. Con­sider the small­est right end­point in $I^\star$. Sup­pose this comes from in­ter­val $[a_i,b_i]$ so that $I^\star$ does not con­tain any of $[a_1,b_1],\ldots,[a_{i-1},b_{i-1}]$. But this means $I^\star$ does not con­tain any in­ter­val that in­ter­sects $[a_1,b_1]$ ex­cept pos­si­bly $[a_i,b_i]$.

....

A $(1-\eps)$-Ap­prox­i­ma­tion

The $\frac{1}{2}$-ap­prox­i­ma­tion al­go­rithm given above can be gen­er­al­ized to give a $1-\ep­silon$ ap­prox­i­ma­tion for any $\ep­silon>0$. Here's the idea.

1. Draw a set of hor­i­zon­tal lines $L_1,\ldots,L_k$ as in the pre­vi­ous al­go­rithm. For each $i\in\{1,\ldots,k\}$, let $S_i$ be the sub­set of rec­tan­gles in­ter­sected by $L_i$. For other val­ues of $i$, de­fine $S_i = \emp­ty­set$.
2. For each $i\in\{1,\ldots,k\}$, find an MIS, $I_i$, of $S_i\cup S_{i+1}\cup\cdots S_{i+r}$
3. For each $i\in\{1,\ldots,r\}$, let $A_j = \bigcup_{i=1}^{\lfloor k/(r+1)\rfloor} I_{j+(r+1)j}$
4. Out­put the largest among $A_1,\ldots,A_r$.

$I_i$, of $S_i$, for each $i\in\{1,\ldots,k\}$. 3. Out­put $I_1\cup I_3\cup I_5\cup\cdots,\cup I_{2\lceil k/2\rceil-1}$ or $I_2\cup I_4\cup I_6\cup\cdots,\cup I_{2\lfloor k/2\rfloor}$, whichever is big­ger.