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.

Improve this question
$\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$
    – Charles Matthews
    Commented Sep 20, 2010 at 11:13
  • $\begingroup$ I am confused. Doesn't the second figure show that we can do 10 points? $\endgroup$
    – Vinayak Pathak
    Commented 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$
    – Charles Matthews
    Commented Sep 20, 2010 at 13:53
  • $\begingroup$ That shape is called a lune in the computational geometry literature... $\endgroup$
    – Joseph O'Rourke
    Commented Sep 20, 2010 at 15:06

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .