Algorithm to find figures using input points I have just discussed with student and he told me him task, and I think it is interesting.
The task.
There are file with points like:
Point0: x=1; y=4;
Point1: x=199; y=45;
Point2: x=42; y=333;
Point3: x=444; y=444;
...
PointN: x=nnn; y=mmm;

You should find polygons and draw them. Each polygon present as internal
I mean something like this:
---------
| -----  |
| |    | |
| |----| | 
|        |
|--------|

And question what algorithm can you advice to use in this case?
I understand this is from graph theory , but want opinion of other.
Thanks.
 A: Use the Convex Layers algorithm of Bernard Chazelle, which is optimal: $\mathcal{O}(n \log n)$ time.
See here: http://www.cs.princeton.edu/~chazelle/pubs/ConvexLayers.pdf
Here is a snapshot of part of the first page of the paper:

A: This is not an answer, since the problem statement is kind of vague, here is what I assume it is.Assuming a polygon immediately inside a polygon to be the child of the polygon (and similarly for parent)
maximize the number of points utilized to draw polygons such that
1. each polygon contains only one child polygon (no siblings)
2. each polygon has only one immediate parent (doesn't lie in the intersection of 2 or more parents)
Of course, outermost and innermost polygons do not need to satify conditions 2 and 1 respectively.
Again J.M.'s question is important - do you mean polygons or quadrilateral?
A: If what I posted below is a correct assumption, then you could think of a solution on these lines.


*

*find centroid of all points in set S (expensive)

*obtain farthest points from the centroid. 

*use these to draw the outermost polygon. 

*remove from this points from set S

*repeat step 1 until (no more inner polygons can be drawn)
A: There are several algorithms for curve reconstruction from point samples. See for instance http://www.cse.ohio-state.edu/~tamaldey/curverecon.htm and http://valis.cs.uiuc.edu/~sariel/research/CG/applets/Crust/Crust.html
A: I will use Convex_hull
Thanks to all for answers.
