shibly's blog

UVA: 12307 - Smallest Enclosing Rectangle
By shibly, 13 years ago, In English

Smallest Enclosing Rectangle of some points id 2D plane where the number of points is 100000. The points will not be collinear. I need some idea to solve the problem.

Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=278&problem=3729&mosmsg=Submission+received+with+ID+9328461

Thanks.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I suppose that smallest rectangle would necessary have at least one of sides which contains at least two of points on it (and other sides would have at least one point each).

So you may start with searching for convex hull for this set. One of its bordering line would be the same as one of the required rectangle's side. You are just to check each of the hull borders, build minimal rectangle upon it and select minimum of all these rectangles. Though I suppose that you may need to optimize series rectangle building so that if convex hull have M points, you build M rectangles in O(M), not O(N*M).

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot RodionGork. I am trying.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am getting WA. Can you give me more hints?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I fear that it is impossible to give any hint without knowing what are you doing to get WA. There could be few possibilities:
    - proposed algorithm is wrong;
    - your implementation is not correct.

    Does it work correctly for proposed testcase?
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My code works correctly for proposed test cases. Can you send me your code? My mail address is:  maksud_1969@yahoo.com
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I fear I can't. I never saw this problem before you asked and I never tried to implement it. Sorry - my idea is based only on some related problems which I tried to solve in past times. :D
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks again for trying to help me. I saw the same problem before and tried. There may be a way called Rotating calipers . But I have no idea abut that. 

Can any one give me some new idea to solve this problem?

→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You can do the following:


-Build a convex hull

-For each straight line segment(points  [i, i+1]) in the convex hull find the furthest point from it (let it be j)(furthest from the straight line, not just the segment). You can do it in O(N) with two iterators.

So now you know for each line segment the width of the rectangle, if one of its sides passes through that segment (width = distance from the straight line passing through [i, i+1] to point j).

Next step is finding the optimal length for each of the segments. Since you know the furthest point j, you can divide the convex hull into two parts ([i+1..j], [i..j]) and do a ternary search (UPD: or even repeat the same approach with two iterators as before) on each to find the furthest point of the convex hull from a straight line that is perpendicular to [i, i+1] and passes through the point j. Then the length is the distance from the furthest of [i+1..j] to the furthest of [i..j].

Now you know both optimal length and width, so you can easily find the minimum area. (Hope the solution is right)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks a lot ACube. I will try using your logic.
→ Reply