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. Conferences, Workshops, Symposiums, and Seminars
  4. Unsplittable Coverings in the Plane
 
conference paper

Unsplittable Coverings in the Plane

Pach, Janos  
•
Palvolgyi, Domotor  
Mayr, Ew
2016
Graph-Theoretic Concepts In Computer Science
41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-662-53174-7_20
Web of Science ID

WOS:000389704200020

Author(s)
Pach, Janos  
Palvolgyi, Domotor  
Editors
Mayr, Ew
Date Issued

2016

Publisher

Springer-Verlag Berlin

Publisher place

Berlin

Published in
Graph-Theoretic Concepts In Computer Science
ISBN of the book

978-3-662-53174-7

978-3-662-53173-0

Total of pages

16

Series title/Series vol.

Lecture Notes in Computer Science

Volume

9224

Start page

281

End page

296

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Event nameEvent placeEvent date
41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

Garching, GERMANY

JUN 17-19, 2015

Available on Infoscience
January 24, 2017
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/133301
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