NDLI: Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks

Content Provider	Springer Nature Link
Author	Bezdek, András Kuperberg, Włodzimierz
Copyright Year	2008
Abstract	Two convex disks K and L in the plane are said to cross each other if the removal of their intersection causes each disk to fall into disjoint components. Almost all major theorems concerning the covering density of a convex disk were proved only for crossing-free coverings. This includes the classical theorem of L. Fejes Tóth (Acta Sci. Math. Szeged 12/A:62–67, 1950) that uses the maximum area hexagon inscribed in the disk to give a significant lower bound for the covering density of the disk. From the early seventies, all attempts of generalizing this theorem were based on the common belief that crossings in a plane covering by congruent convex disks, being counterproductive for producing low density, are always avoidable. Partial success was achieved not long ago, first for “fat” ellipses (A. Heppes in Discrete Comput. Geom. 29:477–481, 2003) and then for “fat” convex disks (G. Fejes Tóth in Discrete Comput. Geom. 34(1):129–141, 2005), where “fat” means of shape sufficiently close to a circle. A recently constructed example will be presented here, showing that, in general, all such attempts must fail. Three perpendiculars drawn from the center of a regular hexagon to its three nonadjacent sides partition the hexagon into three congruent pentagons. Obviously, the plane can be tiled by such pentagons. But a slight modification produces a (non-tiling) pentagon with an unexpected covering property: every thinnest covering of the plane by congruent copies of the modified pentagon must contain crossing pairs. The example has no bearing on the validity of Fejes Tóth’s bound in general, but it shows that any prospective proof must take into consideration the existence of unavoidable crossings.
Starting Page	187
Ending Page	208
Page Count	22
File Format	PDF
ISSN	01795376
Journal	Discrete & Computational Geometry
Volume Number	43
Issue Number	2
e-ISSN	14320444
Language	English
Publisher	Springer-Verlag
Publisher Date	2008-10-04
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Covering Convex disk Crossing Density Computational Mathematics and Numerical Analysis Combinatorics
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks

Packing and Covering with Centrally Symmetric Convex Disks

The Set of Packing and Covering Densities of Convex Disks

On the Covering Densities of Quarter-Convex Disks

Covering the plane with copies of a convex disk

Packing and Covering with Centrally Symmetric Convex Disks

Covering the Plane with Translates of a Triangle

Best Partial Covering of a Convex Domain by Congruent Circles of a Given Total Area

Finite packing and covering by congruent convex domains

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks

Similar Documents

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks

Packing and Covering with Centrally Symmetric Convex Disks

The Set of Packing and Covering Densities of Convex Disks

On the Covering Densities of Quarter-Convex Disks

Covering the plane with copies of a convex disk

Packing and Covering with Centrally Symmetric Convex Disks

Covering the Plane with Translates of a Triangle

Best Partial Covering of a Convex Domain by Congruent Circles of a Given Total Area

Finite packing and covering by congruent convex domains

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks