algorithm - Finding boundary co-ordinates from given set of point co-ordinates?

Given a set of coordinates, How do we find the boundary coordinates.
<== Figure 1
Given the coordinates in the above set, How can I get the coordinates on the red boundary. Boundary is the polygon which is formed by the input coordinates for vertices, in such a way that it maximizes the area.

I am working on an app which searches properties within 'x' miles of a city. What I have is:

1. Coordinates of all the properties.


2. A set of coordinates for each city (I have one coordinate for each zip. And since most cities have more than one zip, Every city has a set of coordinates)

The reason I am asking for the maximum area is so that I don't come up with a polygon like the one below:

<== Figure 2

What I need is the algorithm to come up with the set of coordinates for the boundary. An algorithm which will allow me to come up with boundary coordinates for Figure 1.

Answer

There are many algorithms to solve this problem (Wikipedia "Convex_hull_algorithms"):

• Gift wrapping aka Jarvis march — O(nh): One of the simplest algorithms. It has O(nh) time complexity, where n is the number of points in the set, and h is the number of points in the hull. In the worst case the complexity is O(n2).


• Graham scan — O(n log n): Slightly more sophisticated, but much more efficient algorithm. If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(n) time. [pseudo code]


• QuickHull: Like the quicksort algorithm, it has the expected time complexity of O(n log n), but may degenerate to O(nh) = O(n2) in the worst case. [illustrated description]


• Divide and conquer — O(n log n): This algorithm is also applicable to the three dimensional case.


• Monotone chain — O(n log n): A variant of Graham scan which sorts the points lexicographically by their coordinates. When the input is already sorted, the algorithm takes O(n) time.


• Incremental convex hull algorithm — O(n log n)


• Marriage-before-conquest — O(n log h): Optimal output-sensitive algorithm.


• Chan's algorithm — O(n log h): Simpler optimal output-sensitive algorithm .