Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Okay, I am in no way a mathematics student but I happened to be writing a program on a map with coordinates of locations displayed on the map.

My problem is that the points could be scattered on the map with an indefinite boundary and I need to find a boundary (rectangle) around these points and thus I need to get a formula to form an algorithm so that the program will find the optimum boundary itself.

I hope this is understandable and thanks in anticipation of any response.

share|improve this question
    
What do you mean by optimum boundary in this case? Are you trying to find a rectangle with minimum perimeter that includes all points of interest? –  svenkatr Dec 5 '10 at 18:54
    
exactly! just like you put it. "minimum perimeter that includes all points of interest" –  Oluwaseyi Daniel Dec 5 '10 at 18:56

1 Answer 1

If the sides of the rectangle must be aligned with the edges of the map, you can just take the maximum and minimum coordinates in each direction. If you allow arbitrary orientation of the rectangle you have a one dimensional minimization problem. You can compute the coordinates of each point as a function of rotation angle, again take the maximum and minimum in each dimension, calculate the perimeter, and minimize over the rotation angle.

If you are not devoted to a rectangle, maybe you would prefer the convex hull of your points. There are efficient algorithms to find it and it doesn't need the minimization. It also has a smaller perimeter yet.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.