2015/02/22 by Farhad Shahrokhi, Shahrokhi, Farhad
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1502.06176
28th European Workshop on Computational Geometry,2012 - Assisi, Perugia, Italy, 269-273
arxiv created 2015/02/22 · arxiv updated 2015/02/24
For \cal C a collection of n objects in Rd, let the packing and piercing numbers of \cal C, denoted by Pack(\cal C), and Pierce(\cal C), respectively, be the largest number of pairwise disjoint objects in \cal C, and the smallest number of points in Rd that are common to all elements of \cal C, respectively. When elements of \cal C are fat objects of arbitrary sizes, we derive sub-exponential time algorithms for the NP-hard problems of computing Pack(\cal C) and Pierce(\cal C), respectively, that run in n^Od(Pack(\cal C)d-1\over d) and n^Od(Pierce(\cal C)d-1\over d) time, respectively, and O(nlog 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((1\overε)d-1) time and O(nlog 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.