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

## Geometry problem

**Moderator:** Board moderators

- Moni
- Experienced poster
**Posts:**202**Joined:**Fri Mar 22, 2002 2:00 am**Location:**Chittagong. CSE - CUET-
**Contact:**

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}

*We are all in a circular way, no advances, only moving and moving!*- Moni
- Experienced poster
**Posts:**202**Joined:**Fri Mar 22, 2002 2:00 am**Location:**Chittagong. CSE - CUET-
**Contact:**

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!

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!

*We are all in a circular way, no advances, only moving and moving!*