Making Octants Colorful and Related Covering Decomposition Problems

Jean Cardinal 1 Kolja Knauer 2 Piotr Micek 3 Torsten Ueckerdt 4
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 Algorithmics Research Group
UJ - Jagiellonian University [Krakow]
Abstract : We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer k, every finite set of points in R^3 can be colored with k colors so that every translate of the negative octant containing at least k^6 points contains at least one of each color. The best previously known bound was doubly exponential in k. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semi-online model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.
Type de document :
Communication dans un congrès
SODA: Symposium on Discrete Algorithms, Jan 2014, Portland, United States. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1424-1432, 2014, Proceedings of SODA '14. 〈https://www.siam.org/meetings/da14/〉. 〈10.1137/1.9781611973402.105〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01414977
Contributeur : Daniel Goncalves <>
Soumis le : lundi 12 décembre 2016 - 17:04:01
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt. Making Octants Colorful and Related Covering Decomposition Problems. SODA: Symposium on Discrete Algorithms, Jan 2014, Portland, United States. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1424-1432, 2014, Proceedings of SODA '14. 〈https://www.siam.org/meetings/da14/〉. 〈10.1137/1.9781611973402.105〉. 〈lirmm-01414977〉

Partager

Métriques

Consultations de la notice

60