Take the 2-minute tour ×

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


share|improve this question
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)? –  Charles Matthews Sep 20 '10 at 11:13
I am confused. Doesn't the second figure show that we can do 10 points? –  Vinayak Pathak Sep 20 '10 at 13:22
Not with distance > 1. But it does show that the area argument cannot be enough by itself to exclude 9. –  Charles Matthews Sep 20 '10 at 13:53
That shape is called a lune in the computational geometry literature... –  Joseph O'Rourke Sep 20 '10 at 15:06

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer


