Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Any polygon, or just quadrilaterals? FWIW, it's easy to figure out if three points determine a triangle. –  J. M. Dec 8 '10 at 13:58
    
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? –  Anthony Labarre Dec 8 '10 at 14:39
add comment

5 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
Oh, Thanks I try to learn this algorithm. –  jitm Dec 8 '10 at 21:28
add comment

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?

share|improve this answer
    
You know, you could have just edited this answer instead of posting another one... –  J. M. Dec 8 '10 at 15:00
    
now I know:) there no way to delete though. –  Prateek Dec 8 '10 at 15:02
add comment

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)
share|improve this answer
add comment

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

share|improve this answer
add comment

I will use Convex_hull

Thanks to all for answers.

share|improve this answer
    
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. –  Aryabhata Dec 8 '10 at 21:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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