Decomposition of Multiple Packings with Subquadratic Union Complexity

DOI10.1017/S0963548315000280zbMATH Open1371.52017arXiv1312.3215MaRDI QIDQ5364271FDOQ5364271

Authors: János Pach, Bartosz Walczak 

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Suppose $k$ is a positive integer and $mathcalX$ is a $k$-fold packing of the plane by infinitely many arc-connected compact sets, which means that every point of the plane belongs to at most $k$ sets. Suppose there is a function $f(n)=o(n^2)$ with the property that any $n$ members of $mathcalX$ determine at most $f(n)$ holes, which means that the complement of their union has at most $f(n)$ bounded connected components. We use tools from extremal graph theory and the topological Helly theorem to prove that $mathcalX$ can be decomposed into at most $p$ ($1$-fold) packings, where $p$ is a constant depending only on $k$ and $f$.

Full work available at URL: https://arxiv.org/abs/1312.3215

Recommendations

• Packing and decomposition problems for polynomial association schemes
• Limited packing and multiple domination problems: polynomial time reductions
• A polyhedral view to generalized multiple domination and limited packing
• scientific article; zbMATH DE number 15160
• Combinatorial and computational aspects of graph packing and graph decomposition
• On the parameterized complexity of compact set packing
• On the complexity of approximating \(k\)-set packing
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Weakly union-free maximum packings
• On the union complexity of families of axis-parallel rectangles with a low packing number

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Cites Work

• Triangle-free geometric intersection graphs with large chromatic number
• Triangle-free intersection graphs of line segments with large chromatic number
• Applications of random sampling in computational geometry. II
• Title not available (Why is that?)
• A separator theorem for string graphs and its applications
• Applications of a New Separator Theorem for String Graphs
• On a Coloring Problem.
• Title not available (Why is that?)
• On the union of fat wedges and separating a collection of segments by a line
• Title not available (Why is that?)
• Title not available (Why is that?)
• Turan's theorem for \(k\)-graphs
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
• Improved bounds on the union complexity of fat objects
• Fat Triangles Determine Linearly Many Holes
• On fat partitioning, fat covering and the union size of polygons
• On the complexity of the union of fat convex objects in the plane
• Lattice double packings in the plane
• Multiple covering of the plane by circles
• Mehrfache gitterförmige Kreislagerungen in der Ebene
• On \(k\)-sets in arrangements of curves and surfaces

Cited In (2)

• Weakly union-free maximum packings
• Local search strikes again: PTAS for variants of geometric covering and packing

This page was built for publication: Decomposition of Multiple Packings with Subquadratic Union Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364271)