The barycenter of a polyline is obtained by finding the midpoints of each line segment and then forming their weighted average using the segment lengths as weights.
For example, consider the "L" shape delineated by the points (0,0), (6,0), (6,12). There are two segments: one of length 6 with midpoint at ( (0+0)/2, (0+6)/2 ) = (3,0) and another of length 12 with midpoint at ( (6+6)/2, (0+12)/2 ) = (6,6). Their length-weighted average coordinates are therefore (x,y) with
x = (6*3 + 12*6) / (6+12) = 5, y = (6*0 + 12*6) / (6+12) = 4.
This differs from the barycenter of the three vertices, which is ( (0+6+6)/3, (0+0+12)/3 ) = (4,4).
(Edit As another example, consider the figure in the question, which although square in shape, is represented as a pentagon determined by the sequence of points (0,0), (1/2,0), (1,0), (1,1), (0,1). The five sides have lengths 1/2, 1/2, 1, 1, 1 and midpoints (1/4,0), (3/4,0), (1,1/2), (1/2,1), and (0,1/2), respectively. Their weighted average therefore equals
[(1/2)*(1/4, 0) + (1/2)*(3/4, 0) + (1)*(1, 1/2) + (1)*(1/2, 1) + (1)*(0, 1/2)] / (1/2+1/2+1+1+1)
= (2/4, 2/4) = (0.5, 0.5)
as one would hope, even though the barycenter of the vertices alone (computed as in #2 above) is (0.5, 0.4).)
The barycenter of a polygon can be obtained by triangulation to decompose it into triangles. The barycenter of a triangle-qua-polygon coincides with the barycenter of its vertices. The area-weighted average of these barycenters is the polygon's barycenter. Triangle areas are readily computed in terms of their vertex coordinates (e.g., in terms of the wedge product of two of the sides). For an illustration of such area calculations, including how to exploit signed (positive or negative) areas, see the section on "Area" at my (old) course notes page.
(Edit Consider the polygon depicted in the question for example. We could triangulate it with triangles ((0,0), (1/2,0), (0,1)) on the left, ((0,1), (1/2,0), (1,1)) in the middle, and ((1,1), (1,0), (1/2,0)) on the right. Their areas are 1/4, 1/2, 1/4 respectively and their barycenters--obtained by averaging their vertices--are (1/6,1/3), (1/2,2/3), and (5/6,1/3), respectively. The area-weighted average of these barycenters equals
[(1/4)*(1/6,1/3) + (1/2)*(1/2,2/3) + (1/4)*(5/6,1/3)] / (1/4 + 1/2 + 1/4)
= (12/24, 6/12)
= (0.5, 0.5)
as it should, despite the presence of that fifth vertex along the bottom edge.)
Best Answer
Some notes too big to put into a comment (though this doesn't suggest an obvious algorithm):
The punch line (EDITED): At least two vertices of the maximum area rectangle must lie on the boundary of the polygon (i.e. along an edge, or at a vertex). And if the maximum area rectangle is not a square, then at least three vertices must lie on the boundary of the polygon.
I proved it to myself in four steps:
Note #1: At least one vertex of the maximum area rectangle will always lie on the boundary of the polygon. This is pretty obvious, but a proof could go like this (by contradiction): Suppose you had a "maximal" rectangle with no vertex on the boundary of the polygon. That means there would be at least a little room around each of its vertices. So you could expand your rectangle a bit, contradicting its maximality.
Note #2: At least two vertices of the maximum area rectangle will always lie on the boundary of the polygon. A proof could go like this (again by contradiction): Suppose you had a "maximal" rectangle with only one vertex on the boundary (guaranteed by Note #1). Consider the two edges not adjacent to that vertex. Since their endpoints are NOT on the boundary, there's a little room around each. So either of those edges could be "extruded" a bit, expanding the polygon's area and contradicting its maximality.
Note #3: There are two diagonally opposite vertices of the maximum area rectangle that lie on the boundary of the polygon. (We know from Note #2 that there are at least two, but not necessarily that they're across from each other.) But again by contradiction, if the only two boundary vertices were adjacent, then the opposite edge (neither of whose vertices are on the boundary) could be extruded a little bit, increasing the area of the rectangle and contradicting its maximality.
Note #4: (EDITED) If the maximum area rectangle is not a square, then three of its vertices will lie on the boundary of the polygon.
To prove, suppose that's not the case, i.e. that the maximum area rectangle is not a square, but only two of its vertices are on the boundary of the polygon. I'll show how to construct a bigger rectangle, contradicting the maximality.
Call the vertices of the rectangle
A,B,C, andD. Without loss of generality, assume thatBandDare the two that are on the polygon boundary. SinceAandCare on the interior of the polygon, there's some wiggle room around them (represented with circles aroundAandCin the picture below). Now draw a circle around the rectangle, and slide pointsAandCa little bit around the circle by the same amount (to makeA'andC', pictured below) so that the new rectangleA'BC'Dis more square than the original rectangle. This process creates a new rectangle that is also within the original polygon and has a larger area. This is a contradiction, so the proof is done.To believe that proof, you have to convince yourself that the area of a rectangle inscribed in a circle increases as it becomes "more square" (i.e. the difference between the edge lengths gets smaller). You also need the polygon to be convex so that the new lines are all within it. And there are probably other little details getting swept under the rug, but I'm fairly sure they all work out.