New separation theorems and sub-exponential time algorithms for packing and piercing of fat objects

For $\mathcal{C}$ a collection of $n$ objects in $R^d$, let the packing and piercing numbers of $\mathcal{C}$, denoted by $Pack(\mathcal{C})$, and $Pierce({\cal C})$,respectively,bethelargestnumberofpairwisedisjointobjectsin${\cal C}$,andthesmallestnumberofpointsin$R^d$ that are common to all elements of $\mathcal{C}$, respectively. When elements of $\mathcal{C}$ are fat objects of arbitrary sizes, we derive sub-exponential time algorithms for the NP-hard problems of computing $Pack(\mathcal{C})$ and $Pierce(\mathcal{C})$, respectively, that run in $n^{O_d({Pack(\mathcal{C})}^{\frac{d-1}{d}})}$ and $n^{O_d({Pierce(\mathcal{C})}^{\frac{d-1}{d}})}$ time, respectively, and $O(n\log n)$ storage. Our main tool which is interesting in its own way, is a new separation theorem. The algorithms readily give rise to polynomial time approximation schemes (PTAS) that run in $n^{O({(\frac{1}{ϵ})}^{d-1})}$ time and $O(n\log n)$ storage. The results favorably compare with many related best known results. Specifically, our separation theorem significantly improves the splitting ratio of the previous result of Chan, whereas, the sub-exponential time algorithms significantly improve upon the running times of very recent algorithms of Fox and Pach for packing of spheres.