2012/03/02 by Adrian Dumitrescu, Dumitrescu, Adrian, Minghui Jiang +1
Computer Science · Mathematics · #52C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Mathematics #Point processes and geometric inequalities #acm:52C10 #math.CO #msc:52C10
paper · pdf · doi:10.48550/arxiv.1203.0563
19 pages, 8 figures; minor update; updated references
openalex publication_date 2012/03/02 · arxiv created 2012/07/27 · arxiv updated 2012/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a planar point-set P, let D(P) be the minimum number of pairwise-disjoint empty disks such that each point in P lies on the boundary of some disk. Further define D(n) as the maximum of D(P) over all n-element point sets. Hosono and Urabe recently conjectured that D(n)=\lceil n/2 \rceil. Here we show that D(n) ≥ n/2 + n/236 - O(√(n)) and thereby disprove this conjecture.