Posted: Sat May 31, 2008 9:33 am
I just see only few people who have solved this problem, however I think this problem it's not so hard. I have thought of a simple algorithm. If I miss something, please point out.
My algorithm is very simple. Just sort all points by their angles in polar coordinate system. Next, try to wrap all points in circular sequence and get a proper hull. In order to get the minimal hull, start wrapping from all different points, and see what is the minimal hull. Besides, the whole wrapping procedure is similar with Graham's scan.
Here is the explanation. However the origin (0,0) is outside of the initial convex hull or not, we can sort all points by their angle in polar coordinate system. If the origin (0,0) is outside of the initial convex hull, it means the origin must be a part of the wanted hull. In addition, the wanted hull is exactly a convex hull. So we can directly use Graham's scan within those well-sorted points. In my algorithm, all proper hulls are enumerated, and they must contain the wanted convex hull which is also the minimal hull. Furthermore, If the origin (0,0) is inside of the initial convex hull, the points are also well-sorted. We still can wrap the points in such sequence.
My algorithm is very simple. Just sort all points by their angles in polar coordinate system. Next, try to wrap all points in circular sequence and get a proper hull. In order to get the minimal hull, start wrapping from all different points, and see what is the minimal hull. Besides, the whole wrapping procedure is similar with Graham's scan.
Here is the explanation. However the origin (0,0) is outside of the initial convex hull or not, we can sort all points by their angle in polar coordinate system. If the origin (0,0) is outside of the initial convex hull, it means the origin must be a part of the wanted hull. In addition, the wanted hull is exactly a convex hull. So we can directly use Graham's scan within those well-sorted points. In my algorithm, all proper hulls are enumerated, and they must contain the wanted convex hull which is also the minimal hull. Furthermore, If the origin (0,0) is inside of the initial convex hull, the points are also well-sorted. We still can wrap the points in such sequence.
