Geometry problem

[DemonCris]

When encountering geometry problem, I always give up
Here are two classical problem for you all to help me ... thx
1. Given lots of arbitray points in two dimention coordinates and a specified diameter
circle. You need to find out at least how many number of circles to cover all these points.

2. Given two arbitrary polygons. You must find out the intersection region of these two
polygons.


For the above two class problems, I completely have no idea

[Moni]

Hai! Don't hate the geometry problems. They are nice like exellent arts

• 1) you can first define a convex hull for that point set. and then fill that polygon with the circles of desired circles. (first intact the whole polygon inside a sqare or rectangle. then you can easily fill the rectangle with circles. after that remove thosecircles that don't contain any of the points.)
  
  2) It is very easy if you are familier with "computational geometry"
  { If you are expert in Calculus specially Integral Calculus and know the equaions of any of the polygons sides you can easily find that.
  
  Besides if you find the intersection polygon (the intersected area is also a polygon) then you can apply "Triangulation Method" to find the area by dividing the polygon in triangles which are very easy to find area}

I am also very interested in geometry. If you are also then must mail me. we may keep in touch with each other

[kcph007]

Hi, good to hear about geometry problems too. but for the first prob, that solution doesn't guarante the minimum number of circles
Cheers

[Moni]

Yes, You are correct! This is a "Greedy Approach". This surely won't give you the optimal result.

But you know that if any three circles (of same radius) touch with each other, then they build a "concave" triangle (Angles equal to each other but less than 60 deg. (It's something like those Reimann Surfaces in 3D but here 2D!) ) among them, you have to sure that no points are in that triangle!

Besides, You have to be given that no circle interlock (overlap) with each other.

I have another idea!

First you can take all the circles of the given radius centering the given points. Then you have the number of circles equal to the number of points given.
Then remove those circles which are already covered by another circle.

I think this is more closer than the previous one but this is still not the optimal!

May be this is packing or tiling related problem! Which generally don't say that this is optimal !!!

Thank! Hmm... You are also a geometry lover!