Tell me more ×
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.
up vote 1 down vote favorite

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

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
up vote 0 down vote

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
up vote 0 down vote

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
up vote 0 down vote

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
up vote 0 down vote

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

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.