Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Unsplittable coverings in the plane
 
research article

Unsplittable coverings in the plane

Pach, Janos  
•
Palvolgyi, Domotor  
2016
Advances In Mathematics

A system of sets forms an m-fold covering of a set X if every point of X belongs to at least m of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density estimates for sphere packings as well as by the planar sensor cover problem. It has been the prevailing conjecture for 35 years (settled in many special cases) that for every plane convex body C, there exists a constant m = m(C) such that every m-fold covering of the plane with translates of C splits into 2 coverings. In the present paper, it is proved that this conjecture is false for the unit disk. The proof can be generalized to construct, for every m, an unsplittable m-fold covering of the plane with translates of any open convex body C which has a smooth boundary with everywhere positive curvature. Somewhat surprisingly, unbounded open convex sets C do not misbehave, they satisfy the conjecture: every 3-fold covering of any region of the plane by translates of such a set C splits into two coverings. To establish this result, we prove a general coloring theorem for hypergraphs of a special type: shift-chains. We also show that there is a constant c > 0 such that, for any positive integer m, every m-fold covering of a region with unit disks splits into two coverings, provided that every point is covered by at most c2(m/2) sets. (C) 2016 Elsevier Inc. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.aim.2016.07.011
Web of Science ID

WOS:000384510600015

Author(s)
Pach, Janos  
Palvolgyi, Domotor  
Date Issued

2016

Publisher

Academic Press Inc Elsevier Science

Published in
Advances In Mathematics
Volume

302

Start page

433

End page

457

Subjects

Multiple covering

•

Sphere packing

•

Hypergraph coloring

•

Cover decomposition

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
November 21, 2016
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/131377
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés