1
$\begingroup$

Given a set of points in a 2D space, there are gazillions of suggestion on how to compute a convex hull. However, in my assignment, we need to add the information about the figure that's going to be produced. In fact, given the somewhat dull nature of the work, we do know that it's going to be a rectangle, triangle or, if things get wild and crazy, a trapezoid.

The convex hull given that it's rectangle is trivial to compute. One only needs to find the extremes of all the points' x and y. However, when it comes to the triangle, I feel a bit confused. It seems that there's a unique convex hull provided that we're supposed to produce a triangle but I can't shake off the feeling that it's actually an ambiguous concept. It gets even less transparent when it comes to the trapezoid.

  1. Is it possible to uniquely determine the convex hull of a set of 2D points given that the resulting figure is a triangle?

  2. And if so, how should I approach the problem?

  3. Is it possible to uniquely determine the convex hull of a set of 2D points given that the resulting figure is a trapezoid?

  4. Is the approach to be similar to triangle case?

There's a suggestion on how to do the triangle part but it has two significant drawbacks. First one being that I don't have access to MatLab (we work with C) and second being that I don't quite follow it, hehe.

$\endgroup$

closed as unclear what you're asking by Crostul, iadvd, Daniel W. Farlow, Parcly Taxel, JonMark Perry Aug 31 '16 at 8:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

0
$\begingroup$

Any of the standard convex hull algorithms will work regardless of the output. If you want to do better than $\Omega(n \log n)$ for situations where the hull has a constant number of points, use an output sensitive algorithm such as Chan's algorithm or the gift wrapping algorithm.

A quick sketch of the gift wrapping algorithm: Start with the leftmost point, then successively add points $p_{i+1}$ such that the all points are to the right of the line $p_ip_{i+1}$.

$\endgroup$
  • $\begingroup$ I'm afraid that I didn't explain it well. The algorithm you present seems to lead to the smallest convex hull (constituting some polygon). I'm looking for a method to create a convex-ish hull, such that it's form is a triangle. I.e. the hull is supposed to contain only three corners, enclose all the points in the set and be the smallest possible area. $\endgroup$ – Konrad Viltersten Aug 30 '16 at 17:41
  • $\begingroup$ Ok, that is not called a convex hull. Instead you are looking for a minimum enclosing triangle/rectangle/trapezoid and you need to specify whether you mean minimum perimeter or minimum area. $\endgroup$ – Michael Biro Aug 30 '16 at 17:46
  • $\begingroup$ Aha, I knew that! I had the sense that it wasn't as straight forward and unambiguous. I guess it's the area I'm looking forward, although, now, that you mention it, it'd be nice to get an answer on both. $\endgroup$ – Konrad Viltersten Aug 30 '16 at 19:25

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