I have N number of circles, all with a radius of 1.
A point P is located *inside* *all* the circles.
How do I find the point Q that is as close as
possible to P, but which is located *outside* *all*
the circles?

Thanks in advance,

Rune

---
Updated January 24: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

I can imagine he solution. I write this as I think, and cannot guarantee a
working solution; only a thorough (?) analysis of the problem.

Preliminary analysis: By a circle we mean not the 2d curve, but the 2d space
_enclosed_ by this curve, but not _including_ the curve. Thus, any point
_inside_ a circle with radius 1 lies _closer_ than 1 units from the centre
of the circle. The point _just outside_, however, will lie exactly one unit
away from the centre.

If you have N circles (not spheres, but the 2d counterpart) in the plane,
with radius 1, you can see this:

We are seeking a point _no farther_ than 1 units away from one well chosen
circle. This, because there are a finite number of circles, and there will
always exist a point that is outside them all.

the vector a_n which points from the centre of circle number n to the point
P (insode) in question, has an absolute value _less_ than 1. The vector b_n,
pointing to the point Q _outside_all of the circles, however, has an
absolute value _equal_ to one.

Examining the perimeter of the union of the circles, we find m candidates to
the point Q, and these lie in the corners where circles meet. There are a
maximum of N+1 such points, but it can be less. (I cannot prove this easily,
but see for yourself; it must be true). Thus we have reduced the amount of
possible solutions from one zillion to N+1, and that's not bad.

It sould not be difficult to locate those points, checking the distance to P
and chose the one(s) closest.

In fact, I think there might be a connection between the closes point and
the vector sum of the vectors b_n and the sum a_n, but I'm not sure.

Hope this was useful/laughable/fun.

Simen.

Rune skrev i meldingen <38a31d99@news.povray.org>...
>I have N number of circles, all with a radius of 1.
>A point P is located *inside* *all* the circles.
>How do I find the point Q that is as close as
>possible to P, but which is located *outside* *all*
>the circles?
>
>Thanks in advance,
>
>Rune
>
>---
>Updated January 24: http://rsj.mobilixnet.dk
>Containing 3D images, stereograms, tutorials,
>The POV Desktop Theme, 350+ raytracing jokes,
>miscellaneous other things, and a lot of fun!
>
>
>

Post a reply to this message

Simen Kvaal wrote:
>I can imagine he solution. I write this as I think, and cannot guarantee a
>working solution; only a thorough (?) analysis of the problem.
>
>Preliminary analysis: By a circle we mean not the 2d curve, but the 2d
space
>_enclosed_ by this curve, but not _including_ the curve. Thus, any point
>_inside_ a circle with radius 1 lies _closer_ than 1 units from the centre
>of the circle. The point _just outside_, however, will lie exactly one unit
>away from the centre.

Yes.

>If you have N circles (not spheres, but the 2d counterpart) in the plane,
>with radius 1, you can see this:
>
>We are seeking a point _no farther_ than 1 units away from one well chosen
>circle. This, because there are a finite number of circles, and there will
>always exist a point that is outside them all.
>
>the vector a_n which points from the centre of circle number n to the point
>P (insode) in question, has an absolute value _less_ than 1. The vector
b_n,
>pointing to the point Q _outside_all of the circles, however, has an
>absolute value _equal_ to one.

Yes, where sphere N is one specific circle, not any circle.

>Examining the perimeter of the union of the circles, we find m candidates
to
>the point Q, and these lie in the corners where circles meet. There are a
>maximum of N+1 such points, but it can be less. (I cannot prove this
easily,
>but see for yourself; it must be true).

I don't think so. If there's holes in the area covered by the spheres there
will be more points, I think.

Besides, How do I find out which intersection points are on the perimeter of
the union? I guess testing all the points are the only way?

One more question: How do I find these points where the circles intersect?

Thanks for your help!

Greetings,

Rune

---
Updated January 24: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

Rune wrote:

> I don't think so. If there's holes in the area covered by the spheres there
> will be more points, I think.

But you said the point is inside *all* of the circles. I am only hypothesizing
here, but I believe if such a point does exist there can be no holes.

--
___     ______________________________________________________
 | \     |_                 <dav### [at] faricynet> <ICQ 55354965>
 |_/avid |ontaine               http://www.faricy.net/~davidf/

"Sitting on a cornflake, waiting for the van to come" -Beatles

Post a reply to this message

Just assume that Q lies on a circle of radius 2 centered at P.

Rune wrote:

> I have N number of circles, all with a radius of 1.
> A point P is located *inside* *all* the circles.
> How do I find the point Q that is as close as
> possible to P, but which is located *outside* *all*
> the circles?
>
> Thanks in advance,
>
> Rune
>
> ---
> Updated January 24: http://rsj.mobilixnet.dk
> Containing 3D images, stereograms, tutorials,
> The POV Desktop Theme, 350+ raytracing jokes,
> miscellaneous other things, and a lot of fun!

Post a reply to this message

>But you said the point is inside *all* of the circles. I am only
hypothesizing
>here, but I believe if such a point does exist there can be no holes.
>


That was my point too. If such a hole exist, then at least two circles
doesn't overlap, thus no common point for _all_ the circles exist.

5k.

Post a reply to this message

"Simen Kvaal" <sim### [at] studentmatnatuiono> writes:
> 
> the vector a_n which points from the centre of circle number n to the point
> P (insode) in question, has an absolute value _less_ than 1. The vector b_n,
> pointing to the point Q _outside_all of the circles, however, has an
> absolute value _equal_ to one.
> 
> Examining the perimeter of the union of the circles, we find m candidates to
> the point Q, and these lie in the corners where circles meet. There are a
> maximum of N+1 such points, but it can be less. 

No. Without loss of generality we assume that all circles are pairwise
different. (If two circles are identical, we remove one of them.)
Since there exists a point that lies inside all circles, two of them
intersect in two points. There are N circles and therefore N*(N-1)/2
unordered pairs of circles. This may lead to up to N*(N-1) intersections.

> It sould not be difficult to locate those points, checking the distance to P
> and chose the one(s) closest.

The closest intersection point may not be the correct solution. It may
lie inside another (third) circle.

A simple but time consuming algorithm may work like this:

1. For every pair of circles find the two intersection points and collect
   them in a list L.
2. For every circle C
3.     For every intersection point P in L
4.        If P is inside C 
5.           Remove P from the list L
6. Find the closest point in L

Thomas

-- 
http://thomas.willhalm.de/ (includes pgp key)

Post a reply to this message

>No. Without loss of generality we assume that all circles are pairwise
>different. (If two circles are identical, we remove one of them.)
>Since there exists a point that lies inside all circles, two of them
>intersect in two points. There are N circles and therefore N*(N-1)/2
>unordered pairs of circles. This may lead to up to N*(N-1) intersections.
>

But most of these intersections are not interesting, because they are
obscured by other circles. On the _perimeter_ of the big buch of circles,
there are a maximum og N+1 points to check.


Try to draw circles on a paper so that all of them overlap at some point,
and see what happens. How many points around the edge of the figure do you
need to count?

>> It sould not be difficult to locate those points, checking the distance
to P
>> and chose the one(s) closest.
>
>The closest intersection point may not be the correct solution. It may
>lie inside another (third) circle.
>

No, because all the intersection points in question are outside all the
circles. (See above.)

Post a reply to this message

Simen Kvaal wrote:
>>But you said the point is inside *all*
>>of the circles. I am only hypothesizing
>>here, but I believe if such a point does
>>exist there can be no holes.
>
>That was my point too. If such a hole
>exist, then at least two circles doesn't
>overlap, thus no common point for _all_
>the circles exist.

Oops... you're right.
I mixed some thoughts together...

Greetings,

Rune

---
Updated January 24: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

Simen Kvaal wrote:
>But most of these intersections are not
>interesting, because they are obscured
>by other circles. On the _perimeter_ of
>the big buch of circles, there are a
>maximum og N+1 points to check.

Why N+1? Why not just N?

If N=5, there would be 5 circles and
thus 5 of these points.

Please explain :-)

Greetings,

Rune

---
Updated January 24: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message