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.

  • 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
    Commented May 16, 2013 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
    Commented May 16, 2013 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. Commented May 16, 2013 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
    Commented May 16, 2013 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.... Commented May 16, 2013 at 15:39

3 Answers 3


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.

  • (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
    Commented May 15, 2013 at 12:06
  • You are right, even if you forgot triangles 2-3-4 and 6-7-8 in the list. Commented May 15, 2013 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
    Commented May 16, 2013 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
    Commented May 17, 2013 at 5:03

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:


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

  • Thanks, finally we could understand your point. We added a demonstration of the problem too.
    – Developer
    Commented May 18, 2013 at 4:46

Based on question discription and all answers to this question as of 14.03.2018, I’ve devised the following algorithm:

  1. Create the graph of triangles from Delanau triangulation. Represent it with adjacency matrix.
  2. Traverse from every triangle on the graph through all available paths. End traversal, if adding another triangle doesn’t retain convexity. On the picture below, we can traverse from triangle 1 to triangle 7 and all points of two triangles will form convex hull. Moving to triangle 8 breaks convexity, because not all points of all three triangles form convex hull. The longest path on picture will be 1-4-2-5-3-6 and the path in reverse order. Save found paths. Paths obtained on this step represent convex hulls consisting of points of either one or multiple triangles.

Graph of triangles traversal

  1. Delete non-unique groups of triangles.
  2. Delete groups of triangles, which are subsets of larger groups.
  3. Find the group of triangles with the largest total area. Save it.
  4. Delete triangles of this group from graph (adjacency matrix).
  5. Repeat 6 previous steps to obtain set of convex hulls with decreasing area. Do step 7 until only groups consisting of just one triangle are left.

The result of algorithm is shown on the picture below:

Set of convex hulls

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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