23:
337:, the problem is equivalent to one of illumination: how many floodlights must be placed outside of an opaque convex body in order to completely illuminate its exterior? For the purposes of this problem, a body is only considered to be illuminated if for each point of the boundary of the body, there is at least one floodlight that is separated from the body by all of the
391:: every two-dimensional bounded convex set may be covered with four smaller copies of itself, with the fourth copy needed only in the case of parallelograms. However, the conjecture remains open in higher dimensions except for some special cases. The best known asymptotic upper bound on the number of smaller copies needed to cover a given body is
378:
of the original hypercube or parallelepiped; because these shapes have 2 vertices, 2 smaller copies are necessary. This number is also sufficient: a cube or parallelepiped may be covered by 2 copies, scaled by a factor of 1/2. Hadwiger's conjecture is that parallelepipeds are the worst case for this
341:
intersecting the body on this point; thus, although the faces of a cube may be lit by only two floodlights, the planes tangent to its vertices and edges cause it to need many more lights in order for it to be fully illuminated. For any convex body, the number of floodlights needed to completely
366: + 1). However, covering a square by smaller squares (with parallel sides to the original) requires four smaller squares, as each one can cover only one of the larger square's four corners. In higher dimensions, covering a
467:
316:
604:
663:
929:
82:
689:
610:
is better than the asymptotic one. In three dimensions it is known that 16 copies always suffice, but this is still far from the conjectured bound of 8 copies.
510:
490:
55:
886:
884:
Huang, Han; Slomka, Boaz A.; Tkocz, Tomasz; Vritsiou, Beatrice-Helen (2022), "Improved bounds for
Hadwiger's covering problem via thin-shell estimates",
823:
87:
397:
1015:
613:
The conjecture is known to hold for certain special classes of convex bodies, including, in dimension three, centrally symmetric polyhedra and
806:
782:
137:
17:
241:
350:
As shown in the illustration, a triangle may be covered by three smaller copies of itself, and more generally in any dimension a
818:
1020:
1005:
774:
515:
121:. There also exists an equivalent formulation in terms of the number of floodlights needed to illuminate the body.
614:
114:
665:, while for bodies with a smooth surface (that is, having a single tangent plane per boundary point), at most
117:
with the original body, and that furthermore, the upper bound of 2 is necessary if and only if the body is a
853:; Markus, Alexander S. (1960), "A certain problem about the covering of convex sets with homothetic ones",
960:
704:
692:
206:
94:
965:
194:
342:
illuminate it turns out to equal the number of smaller copies of the body that are needed to cover it.
1010:
762:
334:
26:
A triangle can be covered by three smaller copies of itself; a square requires four smaller copies
984:
895:
828:
379:
problem, and that any other convex body may be covered by fewer than 2 smaller copies of itself.
128:, who included it on a list of unsolved problems in 1957; it was, however, previously studied by
624:
915:
802:
778:
375:
974:
938:
905:
838:
963:(1955), "Ăśberdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns",
952:
159:
remains unsolved even in three dimensions, though the two dimensional case was resolved by
60:
948:
325:
is a parallelepiped, in which case all 2 of the scalars may be chosen to be equal to 1/2.
187:
110:
668:
374:
by smaller homothetic copies of the same shape requires a separate copy for each of the
850:
766:
495:
475:
371:
141:
118:
40:
943:
999:
988:
867:
794:
338:
125:
176:
102:
22:
179:
156:
919:
821:; Tiba, Marius (2023), "Towards Hadwiger's Conjecture via Bourgain Slicing",
367:
842:
462:{\displaystyle \displaystyle 4^{n}\exp \left({\frac {-cn}{\log(n)}}\right)}
144:—and in some sources the geometric Hadwiger conjecture is also called the
618:
927:
Lassak, Marek (1988), "Covering the boundary of a convex set by tiles",
910:
979:
351:
29:
900:
833:
797:(2005). "3.3 Levi–Hadwiger Covering Problem and Illumination".
311:{\displaystyle K\subseteq \bigcup _{i=1}^{2^{n}}s_{i}K+v_{i}.}
745:
707:
on covering convex bodies with sets of smaller diameter
358: + 1 copies of itself, scaled by a factor of
671:
627:
518:
498:
478:
401:
400:
244:
63:
43:
683:
657:
598:
504:
484:
461:
310:
76:
49:
930:Proceedings of the American Mathematical Society
855:Izvestiya Moldavskogo Filiala Akademii Nauk SSSR
691:smaller copies are needed to cover the body, as
771:Results and Problems in Combinatorial Geometry
733:
321:Furthermore, the upper bound is necessary iff
599:{\displaystyle (n+1)n^{n-1}-(n-1)(n-2)^{n-1}}
133:
8:
887:Journal of the European Mathematical Society
113:can be covered by 2 or fewer smaller bodies
617:. The number of copies needed to cover any
824:International Mathematics Research Notices
978:
942:
909:
899:
832:
670:
649:
634:
626:
621:(other than a parallelepiped) is at most
584:
538:
517:
497:
477:
422:
406:
399:
299:
283:
271:
266:
255:
243:
171:Formally, the Hadwiger conjecture is: If
68:
62:
42:
387:The two-dimensional case was settled by
21:
717:
329:Alternate formulation with illumination
124:The Hadwiger conjecture is named after
88:(more unsolved problems in mathematics)
57:-dimensional convex body be covered by
799:Research Problems in Discrete Geometry
607:
870:(1957), "Ungelöste Probleme Nr. 20",
801:. Springer-Verlag. pp. 136–142.
769:(1985). "11. Hadwiger's Conjecture".
729:
727:
725:
723:
721:
136:. Additionally, there is a different
7:
817:Campos, Marcelo; van Hintum, Peter;
388:
160:
129:
492:is a positive constant. For small
226:lie in the range 0 <
18:Hadwiger conjecture (graph theory)
14:
944:10.1090/s0002-9939-1988-0958081-7
193:, then there exists a set of 2
32:Unsolved problem in mathematics
793:Brass, Peter; Moser, William;
734:Brass, Moser & Pach (2005)
642:
628:
581:
568:
565:
553:
531:
519:
448:
442:
150:Hadwiger–Levi covering problem
1:
1016:Unsolved problems in geometry
134:Gohberg & Markus (1960)
1037:
775:Cambridge University Press
658:{\displaystyle (3/4)2^{n}}
15:
84:smaller copies of itself?
615:bodies of constant width
235: < 1, and
146:Levi–Hadwiger conjecture
961:Levi, Friedrich Wilhelm
872:Elemente der Mathematik
763:Boltjansky, Vladimir G.
685:
659:
600:
506:
486:
463:
312:
278:
95:combinatorial geometry
78:
51:
27:
966:Archiv der Mathematik
686:
660:
601:
507:
487:
464:
313:
251:
79:
77:{\displaystyle 2^{n}}
52:
25:
843:10.1093/imrn/rnad198
746:Campos et al. (2023)
669:
625:
516:
496:
476:
398:
370:or more generally a
242:
61:
41:
1021:Eponyms in geometry
851:Gohberg, Israel Ts.
705:Borsuk's conjecture
684:{\displaystyle n+1}
512:the upper bound of
207:translation vectors
138:Hadwiger conjecture
132:and independently,
99:Hadwiger conjecture
980:10.1007/BF01900507
777:. pp. 44–46.
681:
655:
596:
502:
482:
459:
458:
354:may be covered by
308:
74:
47:
28:
1006:Discrete geometry
911:10.4171/jems/1132
808:978-0-387-23815-9
784:978-0-521-26923-0
505:{\displaystyle n}
485:{\displaystyle c}
452:
50:{\displaystyle n}
1028:
991:
982:
955:
946:
922:
913:
903:
894:(4): 1431–1448,
879:
862:
845:
836:
812:
788:
749:
743:
737:
731:
695:already proved.
690:
688:
687:
682:
664:
662:
661:
656:
654:
653:
638:
605:
603:
602:
597:
595:
594:
549:
548:
511:
509:
508:
503:
491:
489:
488:
483:
468:
466:
465:
460:
457:
453:
451:
434:
423:
411:
410:
317:
315:
314:
309:
304:
303:
288:
287:
277:
276:
275:
265:
167:Formal statement
101:states that any
83:
81:
80:
75:
73:
72:
56:
54:
53:
48:
33:
1036:
1035:
1031:
1030:
1029:
1027:
1026:
1025:
996:
995:
959:
926:
883:
866:
849:
816:
809:
792:
785:
767:Gohberg, Israel
761:
758:
753:
752:
744:
740:
732:
719:
714:
701:
667:
666:
645:
623:
622:
606:established by
580:
534:
514:
513:
494:
493:
474:
473:
435:
424:
418:
402:
396:
395:
385:
348:
331:
295:
279:
267:
240:
239:
234:
225:
216:
205:and a set of 2
204:
188:Euclidean space
169:
111:Euclidean space
91:
90:
85:
64:
59:
58:
39:
38:
35:
31:
20:
12:
11:
5:
1034:
1032:
1024:
1023:
1018:
1013:
1008:
998:
997:
994:
993:
973:(5): 369–370,
957:
937:(1): 269–272,
924:
881:
868:Hadwiger, Hugo
864:
857:(in Russian),
847:
819:Morris, Robert
814:
807:
790:
783:
757:
754:
751:
750:
738:
716:
715:
713:
710:
709:
708:
700:
697:
680:
677:
674:
652:
648:
644:
641:
637:
633:
630:
593:
590:
587:
583:
579:
576:
573:
570:
567:
564:
561:
558:
555:
552:
547:
544:
541:
537:
533:
530:
527:
524:
521:
501:
481:
470:
469:
456:
450:
447:
444:
441:
438:
433:
430:
427:
421:
417:
414:
409:
405:
384:
381:
372:parallelepiped
347:
344:
339:tangent planes
330:
327:
319:
318:
307:
302:
298:
294:
291:
286:
282:
274:
270:
264:
261:
258:
254:
250:
247:
230:
221:
217:such that all
212:
200:
168:
165:
142:graph coloring
119:parallelepiped
86:
71:
67:
46:
36:
30:
13:
10:
9:
6:
4:
3:
2:
1033:
1022:
1019:
1017:
1014:
1012:
1009:
1007:
1004:
1003:
1001:
990:
986:
981:
976:
972:
968:
967:
962:
958:
954:
950:
945:
940:
936:
932:
931:
925:
921:
917:
912:
907:
902:
897:
893:
889:
888:
882:
877:
873:
869:
865:
860:
856:
852:
848:
844:
840:
835:
830:
826:
825:
820:
815:
810:
804:
800:
796:
791:
786:
780:
776:
773:. Cambridge:
772:
768:
764:
760:
759:
755:
747:
742:
739:
735:
730:
728:
726:
724:
722:
718:
711:
706:
703:
702:
698:
696:
694:
678:
675:
672:
650:
646:
639:
635:
631:
620:
616:
611:
609:
608:Lassak (1988)
591:
588:
585:
577:
574:
571:
562:
559:
556:
550:
545:
542:
539:
535:
528:
525:
522:
499:
479:
454:
445:
439:
436:
431:
428:
425:
419:
415:
412:
407:
403:
394:
393:
392:
390:
383:Known results
382:
380:
377:
373:
369:
365:
361:
357:
353:
345:
343:
340:
336:
328:
326:
324:
305:
300:
296:
292:
289:
284:
280:
272:
268:
262:
259:
256:
252:
248:
245:
238:
237:
236:
233:
229:
224:
220:
215:
211:
208:
203:
199:
196:
192:
189:
186:-dimensional
185:
181:
178:
174:
166:
164:
162:
158:
153:
151:
147:
143:
139:
135:
131:
127:
126:Hugo Hadwiger
122:
120:
116:
112:
109:-dimensional
108:
104:
100:
96:
89:
69:
65:
44:
24:
19:
970:
964:
934:
928:
891:
885:
875:
871:
858:
854:
822:
798:
770:
741:
612:
471:
386:
363:
359:
355:
349:
333:As shown by
332:
322:
320:
231:
227:
222:
218:
213:
209:
201:
197:
190:
183:
172:
170:
154:
149:
145:
123:
106:
98:
92:
1011:Conjectures
861:(76): 87–90
795:Pach, János
389:Levi (1955)
161:Levi (1955)
140:concerning
130:Levi (1955)
103:convex body
1000:Categories
901:1811.12548
834:2206.11227
756:References
335:Boltyansky
180:convex set
157:conjecture
115:homothetic
37:Can every
16:See also:
989:121459171
920:1435-9855
589:−
575:−
560:−
551:−
543:−
440:
426:−
416:
368:hypercube
253:⋃
249:⊆
699:See also
619:zonotope
376:vertices
346:Examples
953:0958081
352:simplex
195:scalars
182:in the
177:bounded
175:is any
987:
951:
918:
805:
781:
472:where
148:or the
97:, the
985:S2CID
896:arXiv
878:: 121
829:arXiv
712:Notes
916:ISSN
803:ISBN
779:ISBN
693:Levi
155:The
975:doi
939:doi
935:104
906:doi
839:doi
437:log
413:exp
105:in
93:In
1002::
983:,
969:,
949:MR
947:,
933:,
914:,
904:,
892:24
890:,
876:12
874:,
859:10
837:,
827:,
765:;
720:^
362:/(
163:.
152:.
992:.
977::
971:6
956:.
941::
923:.
908::
898::
880:.
863:.
846:.
841::
831::
813:.
811:.
789:.
787:.
748:.
736:.
679:1
676:+
673:n
651:n
647:2
643:)
640:4
636:/
632:3
629:(
592:1
586:n
582:)
578:2
572:n
569:(
566:)
563:1
557:n
554:(
546:1
540:n
536:n
532:)
529:1
526:+
523:n
520:(
500:n
480:c
455:)
449:)
446:n
443:(
432:n
429:c
420:(
408:n
404:4
364:n
360:n
356:n
323:K
306:.
301:i
297:v
293:+
290:K
285:i
281:s
273:n
269:2
263:1
260:=
257:i
246:K
232:i
228:s
223:i
219:s
214:i
210:v
202:i
198:s
191:R
184:n
173:K
107:n
70:n
66:2
45:n
34::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
