Convex polygons are self-coverable
From MaRDI portal
Publication:741609
DOI10.1007/S00454-014-9582-9zbMATH Open1302.52002arXiv1307.2411OpenAlexW2025955201MaRDI QIDQ741609FDOQ741609
Authors: Balázs Keszegh, Dömötör Pálvölgyi 
Publication date: 12 September 2014
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Abstract: We introduce a new notion for geometric families called self-coverability and show that homothets of convex polygons are self-coverable. As a corollary, we obtain several results about coloring point sets such that any member of the family with many points contains all colors. This is dual (and in some cases equivalent) to the much investigated cover-decomposability problem.
Full work available at URL: https://arxiv.org/abs/1307.2411
Recommendations
Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Convex sets in (2) dimensions (including convex curves) (52A10)
Cites Work
- Concrete and abstract Voronoi diagrams
- Indecomposable coverings with homothetic polygons
- Octants are cover-decomposable into many coverings
- Making triangles colorful
- Octants are cover-decomposable
- Making Octants Colorful and Related Covering Decomposition Problems
- Survey on Decomposition of Multiple Coverings
- Deciding soccer scores and partial orientations of graphs
Cited In (6)
- An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes
- Coloring Delaunay-edges and their generalizations
- Proper coloring of geometric hypergraphs
- Unsplittable coverings in the plane
- Coloring points with respect to squares
- Indecomposable coverings with homothetic polygons
This page was built for publication: Convex polygons are self-coverable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741609)
