2

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

Spektre
  • 49,595
  • 11
  • 110
  • 380
Projekat Pr
  • 37
  • 4
  • Please show what code you've already tried. – Yserbius Jul 01 '21 at 20:19
  • @Yserbius I did a bitonic binary search, so I found a a greatest distance for every edge. By for loop I have iterated trough all edges and found minimal distance from maximal distances (for every edge). So I found minimal width track. Now I only want to prove that, this track is in one of the minimum bounding boxes. By doing a lot of examples I saw this is case, but how to prove that? So to sum I need a prove correctness of that lemma ž – Projekat Pr Jul 01 '21 at 20:35
  • see [2D OBB](https://stackoverflow.com/a/42997918/2521214) – Spektre Jul 02 '21 at 07:45

2 Answers2

2

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.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
1

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).