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.

  • $\begingroup$ Any polygon, or just quadrilaterals? FWIW, it's easy to figure out if three points determine a triangle. $\endgroup$ – J. M. is a poor mathematician Dec 8 '10 at 13:58
  • $\begingroup$ Also, google "convex hull". Otherwise, I'm having trouble understanding your question. Do you want to find a polygon that contains all your points? Or a set of polygons? Or something else with other constraints? $\endgroup$ – Anthony Labarre Dec 8 '10 at 14:39

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:

alt text

  • $\begingroup$ Oh, Thanks I try to learn this algorithm. $\endgroup$ – jitm Dec 8 '10 at 21:28

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?

  • $\begingroup$ You know, you could have just edited this answer instead of posting another one... $\endgroup$ – J. M. is a poor mathematician Dec 8 '10 at 15:00
  • $\begingroup$ now I know:) there no way to delete though. $\endgroup$ – Prateek Dec 8 '10 at 15:02

If what I posted below is a correct assumption, then you could think of a solution on these lines.

  1. find centroid of all points in set S (expensive)
  2. obtain farthest points from the centroid.
  3. use these to draw the outermost polygon.
  4. remove from this points from set S
  5. repeat step 1 until (no more inner polygons can be drawn)

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


I will use Convex_hull

Thanks to all for answers.

  • $\begingroup$ There is something better than Convex hull (which is $\mathcal{O}(n^2 \log n)$, while optimal is $\mathcal{O}(n \log n)$) in the worst case. See my answer. $\endgroup$ – Aryabhata Dec 8 '10 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.