Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

A set of 2D Points are scattered randomly (i.e., no specified pattern), we are interested in finding all inner-convex-hulls (ICH) in an order of largest in area to a minimum until the entire study area to be covered by set of ICHs, if possible.

As shown in the following figure, it appears that the green convex-hull is the largest possible inner one. We mean inner implying that no point can be inside in the desired convex-hull. The boundary condition for the region can be a normal (i.e., conventionally recognised) convex-hull for all points. In Figure for the first largest in area inner-convex-hull #1 is selected first. The area covered by #1 is then excluded to avoid overlapping problem of the next generations. It seems a bit confusing and hard, hope Figure helps. We guess may be the concept of largest enclosed ellipse could help. It is however a starting guess.

enter image description here

Update 1:
Well the result of our implementation of the idea given below by Uffe Kousgaard is here:

enter image description here

Numbers are ranks i.e., smaller number, larger area. It shows working, however, we noticed several cases the result is not correct. It may be due to bugs in our implementation or the method as noted by whuber below as comment.

Here is result of the method mentioned by Uffe applied on whuber's data:

enter image description here

Apparently something does NOT work well!

Update 2:
The correct complete solution is as follows (for whuber's example data): enter image description here

There are three stages, therefore, to complete the solution. We apply the method fully on each stage. That is, at stage one when all triangles were visited for possible largest inner convex-hull, the selected ICH is stored and the obsolete associated edges/points are removed from data. The procedure starts again for the remaining data. Found a solution, the steps just mentioned above apply. After exhausting all iterations (in a lucky situation as here) the area is fully covered by ICHs (here by 3 ICH) which is our ultimate goal. Note that the given answers so far are only one iteration.

Here we show our understanding of whuber's comment/answer. enter image description here

He was correct that greedy approach won't work as demonstrated above. This disqualifies Uffes idea as a fully correct solution, unfortunately. It looks more challenging thus compared to the initial thoughts.

share|improve this question
    
The illustration of my counterexample is not quite correct. The counterexample assumed a triangulation, which does not permit you to add more triangles beyond those already delineated by the line segments named. In particular, your triangles (3) and (4) are not part of any valid solution. –  whuber May 16 '13 at 4:18
    
The above illustration is the actual result of our implementation of Uffe's idea. Apparently, as we also mentioned there are some problems :( –  Developer May 16 '13 at 5:37
    
Bill, What is wrong with (3) ? It is made up of (6,5,7,8). It should be as valid as your (1,3,4,5,7,8) optimum solution. –  Uffe Kousgaard May 16 '13 at 6:07
    
@Uffe: no, (3) contains a line segment not included in the original triangulation. For the purposes of this example it is invalid to include any additional line segments in the solution. Although I excluded them by fiat to make the example small, they can easily be excluded in actual test cases simply by sprinkling in some extra points within those triangles. –  whuber May 16 '13 at 14:02
    
The original and real triangulation contains it. You just ran out of characters in the comment. But it is still there. Absurd.... –  Uffe Kousgaard May 16 '13 at 15:39

2 Answers 2

This is a comment but could be considered partial progress towards a solution insofar as it might steer the conversation away from a suboptimal technique.

A greedy algorithm based on a triangulation will not always work. As a counterexample, consider the collection of red and blue points in this figure:

Figure

A partial triangulation is shown: extend it in any way you please to the red points. This triangulation uses only the blue points, at coordinates ((-2,-1),(-1,-4),(0,-1),(2,-1),(2,1),(1,4),(0,1),(-2,1)) (in order, as numbered "1" through "8"). The triangles with termini at "2" and "6" each have area 3 (call these the "large" triangles"); the other four triangles have area 2.

It is easy to see that the "inner hull" of maximal area is the rectangle 1458, of area 8. However, any greedy algorithm will be sure to pick up at least one large triangle, but not both of them. But as soon as it includes one, it can include at most two of the other triangles, limiting the area of its solution to 7, which is non-optimal. A few of the red points might additionally be included, but obviously that will add only an inconsequential area: the solution will remain non-optimal.

Note that this example can be altered by moving points 2 and 6 closer to the other points (in near-vertical directions) until the large triangles have areas only slightly greater than 2. It can also be altered by including more red points within triangles 678 and 123, making their contribution to any optimum completely negligible. Accordingly, this construction shows that the greedy algorithm can produce solutions of area 6+e, for tiny values of e, when the optimum solution has area 8.


Another contribution of this reply is to share this method of constructing useful small examples to work with: by sprinkling large numbers of tightly-spaced points in key areas, we can effectively eliminate those areas from possible solutions. This allows us to focus on arbitrary point sets (and their triangulations), of any shape, without having to consider their entire convex hulls. (In this example, the red points eliminated triangles 687 and 243 from consideration in the solution.)

share|improve this answer
    
Thanks, finally we could understand your point. We added a demonstration of the problem too. –  Developer May 18 '13 at 4:46

One solution could be this one:

1) Calculate a triangulation of the whole area.

2) For each triangle, test if inclusion of neighbouring triangles retains the convexity. If more than 1, pick the neighbour, that adds the most to the area. Run the test again with a new set of neighbouring triangles.

I don't know if this will actually find the largest ICH, but it should be a good candidate.

share|improve this answer
    
(A) The solution will depend on the triangulation. (B) One would also not expect this greedy algorithm to be optimal: a few large triangles sticking out along the perimeter can "trap" it into inferior solutions. As a counterexample, consider the points ((-2,-1),(-1,-4),(0,-1),(2,-1),(2,1),(1,4),(0,1),(-2,1)) with the triangulation {(1,2,3),(3,4,5),(5,6,7),(5,7,3),(7,8,1),(1,3,7)} (those are indexes into the point list). The two large triangles (1,2,3) and (5,6,7) attract all greedy solutions and prevent the unique optimum (1,3,4,5,7,8) from being found. –  whuber May 15 '13 at 12:06
    
You are right, even if you forgot triangles 2-3-4 and 6-7-8 in the list. –  Uffe Kousgaard May 15 '13 at 15:54
    
Our experiment as shown in update gives promising results, however, there are some cases that the result of algorithm is not correct. Also note that it is very slow. Nevertheless, it is a nice idea. We appreciated by an upvote so. –  Developer May 16 '13 at 2:58
    
Note that this is not a complete solution but just an idea. As mentioned in the question, once the first largest convex found, it must be removed from data somehow and the procedure needs to be repeated as long as required. Even if you implement the complete solution (which is not an easy task, BTW) in addition to some incorrect results (sometimes) the method is not optimum. –  Developer May 17 '13 at 5:03

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.