0
$\begingroup$

Description edited after comments:

Let's say I have a 3d cuboid that I projected onto a 2d plane. Now I want to find the minimum-area parallelogram that contains all those projected vertices. How do I go about doing that?

$\endgroup$
5
  • $\begingroup$ I'm new around here, so I'm not sure why people are downvoting my question. Perhaps you can write a comment saying what I did wrong to warrant those downvotes? $\endgroup$
    – Moody
    Sep 14, 2017 at 21:26
  • $\begingroup$ Your question is not entirely clear. I tried to answer one interpretation, but I may be reading more into it than is there. $\endgroup$ Sep 14, 2017 at 22:17
  • $\begingroup$ @JosephO'Rourke I project a cuboid onto a 2D plane, then I want to find the minimum-area parallelogram (on that plane) that encompasses all the projected points. Is that what you understood from my question? $\endgroup$
    – Moody
    Sep 14, 2017 at 22:27
  • 1
    $\begingroup$ The body asks for a "minimum-area plane", which makes no sense, as all planes have infinite area. Then you ask for a "4-point convex hull", but it's not at all clear what this means, since there's no reason to expect a 2-dimensional shape to have a convex hull with four vertices. Then in your comment it seems you're not projecting any old 3-dimensional shape, but a cuboid, and you don't want any old 4-cornered set, but a parallelogram. Please think through your question, and edit the body so it asks what you actually want to ask. $\endgroup$ Sep 14, 2017 at 22:55
  • 1
    $\begingroup$ @GerryMyerson I edited the question. I hope that makes it clearer. $\endgroup$
    – Moody
    Sep 14, 2017 at 23:05

1 Answer 1

3
$\begingroup$

(I deleted my first answer, which misinterpreted the original question. Here I address the question in the comments, which is now incorporated in the revised question.)

The minimum area parallelogram enclosing a convex polygon can be found in linear time, linear in the number of vertices (for your case, a small constant). This result depends on proving that two adjacent edges of an optimal parallelogram must be flush with edges of the convex polygon. Once you have that lemma, it is easy to walk through the few possibilities.

Christian Schwarz, Jürgen Teich, Alek Vainshtein, Emo Welzl, and Brian L. Evans. Minimal enclosing parallelogram with application. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages C34–C35, 1995. ACM link.


          enter image description here
          Fig.2. Illustration of proof of one lemma.

Finding the minimum perimeter enclosing parallelogram (not what was asked) is a bit more involved, but can also be found in linear time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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