Inaba's Covering Problem
Script error: No such module "Draft topics".
Script error: No such module "AfC topic".
Inaba's Covering Problem, or Inaba's Coin-Covering Problem, is a problem in geometry based on the 10 Points puzzle by Japanese puzzle maker Naoki Inaba that asks how many points in the Euclidean plane are needed such that no covering using non-overlapping unit disks exists.
Known Bounds[edit]
Inaba introduced the problem in 2008 with a proof that 10 points is not enough using the probabilistic method.[1]
In 2010, in private communications, Peter Winkler proved that 12 points is not enough, and proved an example with 60 points.
In 2011, an example was proven using 52 points.[2]
In 2012, a proof that 12 points is not enough was published, and an example was proven using 50 points, along with a configuration of 45 points found by computer search.[3]
References[edit]
- ↑ Inaba, Naoki (2008). "10 Points Answer". Inaba Puzzle.
- ↑ Okayama, Yosuke; Kiyomi, Masashi; Uehara, Ryuhei (10 Aug 2011). "On covering of any point configuration by disjoint unit disks" (PDF). CCCG.
- ↑ Aloupis, Greg; Hearn, Robert A.; Iwasawa, Hirokazu; Uehara, Ryuhei (8 Aug 2012). "Covering Points with Disjoint Unit Disks" (PDF). CCCG.
- ↑ Winkler, Peter (Aug 2010). "Puzzled: Figures on a Plane". Communications of the ACM. 53 (8): 128. doi:10.1145/1787234.1787260. Unknown parameter
|s2cid=ignored (help)
This article "Inaba's Covering Problem" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Inaba's Covering Problem. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
