Disjoint empty disks supported by a point set |
| |
| Authors: | Adrian Dumitrescu Minghui Jiang |
| |
| Affiliation: | 1. Department of Computer Science, University of Wisconsin–Milwaukee, 3200 N. Cramer Street, Milwaukee, WI, 53211, USA
2. Department of Computer Science, Utah State University, 4205 Old Main Hill, Logan, UT, 84322, USA
|
| |
| Abstract: | 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) geq n/2 + n/236 - O(sqrt{n})}$ and thereby disprove this conjecture. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
