Decomposition of Multiple Packings with Subquadratic Union Complexity

DOI10.1017/S0963548315000280MaRDI QIDQ5364271zbMATHFDO

Authors János Pach, Bartosz Walczak

Publication date 4 October 2017

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

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

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

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)