3
$\begingroup$

Given two closed disks of unit radius, such that center of one lies on the circumference of the other, let M denote their union. We want to place the maximum number of points in M such that their pairwise distance is strictly greater than 1. We can show that we cannot place 10 points, and we have examples where we can place 8. Is it possible to place 9 points? We have not been able to prove that 9 points is impossible. Any suggestions welcome. (I cannot seem to place image tags since this is my first question.. but the images showing why 10 points are impossible and a configuration showing 8 points are available at:

http://www.freeimagehosting.net/image.php?3c080eeea5.jpg, and http://www.freeimagehosting.net/image.php?7ff64600b3.jpg

respectively.

$\endgroup$
4
  • $\begingroup$ The intersection shape is called "vesica piscis" (mathworld.wolfram.com/VesicaPiscis.html). Its area is known, and so the area of the union is known. What does the area argument give (i.e. take the minimum area of a radius-0.5 circle intersected with the shape, and multiply by 9, and compare)? $\endgroup$ Sep 20, 2010 at 11:13
  • $\begingroup$ I am confused. Doesn't the second figure show that we can do 10 points? $\endgroup$ Sep 20, 2010 at 13:22
  • 2
    $\begingroup$ Not with distance > 1. But it does show that the area argument cannot be enough by itself to exclude 9. $\endgroup$ Sep 20, 2010 at 13:53
  • $\begingroup$ That shape is called a lune in the computational geometry literature... $\endgroup$ Sep 20, 2010 at 15:06

1 Answer 1

1
$\begingroup$

Granted that there can be at most 5 in each disc, and a maximum of 2 in the intersection, the case of 2 in the intersection can only be from a total of at most 8. So look at the case of 1 point in the intersection. This reduces to showing at most 3 points possible in certain differences of discs. Now this might well follow from area considerations. It is anyway starting to look plausible in a picture.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.