Minimum area bounding rectangle contains minimum distance track of convex hull

user_16360683 0
Viewed 154

I am working on some project and I have stuck at proving that minimum area bounding rectangle contains 2 edges ( have 2 edges identical) same as minimum distance track of convex hull ( that contains all points of convex hull). Minimum distance track of convex hull is found by: From all edges find the point of convex hull with the most distance of that point and store it in the vector dist. Then take the edge and point that have min value from dist. At the end make parallel line to selected edge trough the selected point. Now I have to prove that minimum bounding rectangle contains 2 edges, that I got in min distance track. Any Idea how to do that is very welcome.

Minimum track in blue line:

img

Minimum bounding rectangle:

img

computational-geometry linear-algebra vector geometry algorithm
2 Answers

You can't prove it, because it's not true. Here's a counter-example:

enter image description here

The area of Triangle 1 is its base*height/2. Let's consider the 3 possible bases: A, B, and C.

For each base, you can form a bounding box for Triangle 1 that includes that base. In each case, the bounding box of Triangle 1 has area base*height, and Triangle 1 takes up exactly half of it, so all of those bounding boxes are the same size.

However, only in one case -- base A, does that bounding box include the entire figure, including Triangle 2. Therefore any bounding box for the entire figure that includes line C must be bigger. Similarly, any bounding box that includes D must be bigger.

However, the minimum width track that includes the entire figure obviously does include C or D, so the minimum width track does not share edges with the minimum bounding box.

user_54835260

Hint:

If the rectangle that you determine is the same as that obtained by rotating calipers (which I believe is true), then that rectangle contains a side and three other vertices.

Then it should be possible to show that if a rectangle contains four vertices but no side, you can rotate it slightly so that the area decreases (in other terms, the derivative of the area on the angle is nonzero).

user_11965490
Related