I need to compute the largest inscribed axis aligned rectangle in a convex polygon so I've been following the algorithms laid out in this paper. Using the prune and search method I can narrow the polygon down to the relevant vertices and edges for the two and three vertex rectangles. What isn't clear is: how is the largest inscribed rectangle constructed from those vertices and edges?
I also found this website which goes into a bit more detail on the algorithms covered in the paper. It still isn't clear how the rectangles are formed as for the two corner case it says
If an edge remains on both A and C, from lemma 1, we consider this to be four instances of the case with an edge and a vertex
I simply don't see how there would be four instances as opposed to two. A is a corner and C an edge and C is a corner and A is an edge. Not sure what the two other cases referenced would be.
Additionally, in the three corner case the website says
Other candidates will be contain at least one vertex so we can examine all six of them (two for each edge in A, B and C) and keep only the valid ones
Which once again seems to be double the amount I would except but this is probably the same issue as the two corner case. It also mentions that
First, there may exist a solution that contains no vertices of P. For this candidate, we need to extend the the edges containing a,b, and c into lines that will intersect to form a triangle. If we parametrize the area as a function of the position of b, we get that the area is maximized when b is located exactly in the middle of its corresponding triangle edge
I have tested this approach; however, the answer it produces seems wrong just by inspection i.e. I used a polygon defined by (0, 0), (1, 3), (5, 2), (3, -1) and the rectangle produced had an area of ~5.8 whereas by inspection I could produce rectangles with an area of ~6.8.
EDIT: Looked into this a bit more and it seems like the area being maximized when b is in the middle of its corresponding triangle edge likely comes from here but that seems to suggest area is maximized when the point lies in the middle of the two sides of the triangle as opposed to the base. I don't see how it is possible to assume the b segment isn't the base of the triangle and thus the point should lie at the midpoint of the a or c segment (although in the example I gave that point is outside the polygon in all cases so that doesn't seem t work either).
EDIT2: Unfortunately haven't had a lot of time to look into this problem but I suspect this paper describes the process to compute the largest rectangle for the three corner case using different terminology.
Three Dependent Sliding Contacts: The case of three dependent sliding contacts is depicted in Figure 4(b). It is dealt with in a manner similar to the case of two dependent sliding contacts. See [12] for details
Which points to this earlier article by the same authors. Once I have time to read through that paper I'll most likely provide another update.