Smallest 4-sided polygon surrounding convex hull ( smallest convex quadrilateral)

[tyberiu...@coonabibba.de]

Hello Group,

I'm trying to implement an image segmentation process, and the paper
I'm working from says:

"Finally the smallest 4-sided polygon surrounding the segmented code [
a convex polygon ] is evaluated. This is a special case of convex hull
evaluation, in which the hull is constrained to have exactly four
sides. The output consists in a list of four points which are the
vertices of a general polygon surrounding the code".

And I can't find an algorithm for that, perhaps because I'm using all
the wrong words.

I believe I'm looking for the minimal enclosing (convex) quadrilateral
(The segments were originally printed as (broken) squares, but
depending on the perspective they were photographed at, they will have
turned into a quadrilateral).

So far I've found
-minimum enclosing rectangle, both axis aligned ( trivial ) and
non-axis aligned (using rotating calipers)
-smallest enclosing paralellogram
-smallest enclosing triangle
-smallest enclosing circle
-somebody else asking roughly the same question (
http://groups.google.com/group/comp.graphics.algorithms/browse_thread/thread/4f75b8190a9bf5ff/0cc38373fa0c1527?lnk=gst&q=quadrilateral&rnum=65#0cc38373fa0c1527
) 13 years ago (without final answer, of course ;) )

So my questions is: does anybody know such an algorithm, or at least
what the problem is really called?

I appreciate your answers,
So long,
Tyberius Prime

[tyberiu...@coonabibba.de]

Hello,

I found there's an algorithm claiming to do solve my problem
in O ( n^2 log k log n):

@article{acy-macp-85
, author = "A. Aggarwal and J. S. Chang and C. K. Yap"
, title = "Minimum area circumscribing polygons"
, journal = "Visual Comput."
, volume = 1
, year = 1985
, pages = "112--117"
, keywords = "extremal figures, polygons"

}

Now all I need to do is understand it and turn it into code;)

So long,
Tyberius Prime