1
$\begingroup$

I want to write an algorithm that find the trapezoid that encloses a set of points (the set is already a convex hull), such that the area of it is minimal.

I've been googling and doodling and I have the impression that at least one side of it is going to be a straight line that is a superset to one of the enclosed polygon's edges.

I'm also almost positive that each of the other three sides will be a superset to an edge of the polygon (like the first one is) or that its middle point will be right at a vertex of the polygon.

Can I make further assumptions? E.g. that there will be two sides that are supersets? Anything else that may be used to additional lower the complexity of the problem?

I have a working algorithm for triangles. Can I reuse it somehow? On one hand, the trapezoid is just a bunch of triangles, so I feel that I can. On the other hand, some portion of such triangles are inside and some other portion is outside the enclosed polygon.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Your second statement is false. It is easy to contrive a set of four points such that there is no trapezoid where all four sides are supersents to one of the four edges defined by the convex hull. For example, $(0,0), (0,100), (1,100), (2,-1)$.

The problem of finding the minimal area trapezoid can be solved in in polynomial time (in fact, in $O(n)$) in the number of points in the convex hull if you first order the points such that the angle from some chosen "first" point, to some selected interior point, to each of the other points is a monotone function of the point number. Once you have that, you can fix, in turn, one of the parallel sides to go through a consecutive pair of points. The minimal trapezoid under that constraint is easy to find; and there are $n$ such choices to evaluate.

$\endgroup$
5
  • $\begingroup$ Thanks for the input. I see the limitation in my reasoning. Apparently, my doodling this far doesn't suffice as a mathematical proof. Let me doodle some more based on your answer and get back to you. :) $\endgroup$
    – Konrad Viltersten
    Commented Sep 13, 2016 at 5:36
  • $\begingroup$ Let me rephrase in layman's terms to verify that I got it correctly. First we make sure that the list of points is clockwise. One of the iterative runs would then be e.g. like this. Pick the side a2a3. Then, the opposite side is trivial (same slope, goes through the point a6). Now, we check the lines a3a4 and a3a5 on the right and a7a1 and a8a1 on the left to see if all the points are enclosed. Wash, rinse, repeat. (There are hairy cases where the slope of the sides would be less than perpendicular that we need to substitute.) Please, pretty please, tell me I got it right. $\endgroup$
    – Konrad Viltersten
    Commented Sep 13, 2016 at 7:26
  • $\begingroup$ Is it clear that at least one of the parallel edges of the minimum area trapezoid will pass through a boundary edge of the convex hull of the set of points? It's not very obvious to me. Think of a very high trapezoid and outside on both parallel edges draw very obtuse isosceles triangles, maybe even similar triangles. What is the minimum area trapezoid containig this set of 6 points? $\endgroup$
    – Futurologist
    Commented Sep 13, 2016 at 12:26
  • $\begingroup$ @Futurologist I have hard time visualizing it. Care to draw a picture and link to it? Or maybe suggest coordinates so I can draw it myself in some convenient software? $\endgroup$
    – Konrad Viltersten
    Commented Sep 19, 2016 at 19:56
  • $\begingroup$ Now I had some time to get into your answer, thanks. In the example provided you clearly prove that not all the sides of the minimal enclosing trapezoid needs to be supersets to the edges of the enclosed convex hull. However, if we conceive that one of the sides, namely the opposing basis to the first side, is only tangental to the vertices of the convex hull, are the remaining two sides also supersets to the edges of the enclosed convex hull? Or can you spawn a counter-example for that too? I.e. example where only one side of the enclosing trapezoid is a superset while the rest are tangents? $\endgroup$
    – Konrad Viltersten
    Commented Sep 19, 2016 at 20:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .