"tessellation" of set of points in 2D with convex polygons

Question

I have a set of points in 2D, that I want to 'triangulate' with the lowest number of convex polygons. Is there an algorithm to do this? (like Delaunay triangulation, but with polygons)

Remarks:

• I have seen many approaches to optimal splitting up of a given set of points into triangles (in 2-D; or simplices in n-D), but none for larger polygons.

• I have also seen many approaches to tessellating the plane with polygons of equal shape and without regarding any previously defined points.

• Voronoi tesselations are always convex; I was wondering if there is a way to find a second set of points, so, that the original set of points forms the vertices of voronoi cells of the first. In that case the voronoi tesselation would be the sought tessellation. I can't quite see it yet.

If someone can point me in the right direction, that would be appreciated.

---

edit 1

Starting from a Delaunay triangulation, I identified all edges that could be removed in a first step.

There are some which are obvious, as they are inside a 4-polygon of which all edges cannot be removed - such as the one indicated by the red arrow. Any final solution will have this edge removed.

However, there are many 'removable' edges that can only be removed if some other removable edge is not removed, and vice versa. Therefor, I need some criterion to select which to keep and which to remove. I was wondering about using circumscribed circles, like some Delaunay algorithms use, but haven't tried it yet. The idea would be to calculate the circumscribed circle for each polygon that results from the removal of a 'candidate' edge - and picking the one that only includes its own points in the resulting polygon. It's not immediately obvious to me, though, if this is necessarily leading to the optimal solution. (It's not even clear to me that the Delaunay triangulation is always a starting point with a path to that solution.) I'm gonna have to give it some more thought.

---

edit 2

I've gone and implemented an algorithm that's a bit shaky but good enough for my purposes; I've added it as an answer. Someone more mathematically gifted is surely able to find a better solution; if so, please do comment / add your own answer.

Answer 1

Answering my own question, kinda.

What I have done: written an algorithm that identifies the edges that can be removed, and which then removes those edges based on a certain criterion: remove the largest edge first, or the edge that creates the most acute angle first.

What I have not done:

• optimized in any way for speed;
• tried to find the 'best' wall to remove, e.g. to end up with the least polygons.

Code (python) can be found here. There is also an option to turn off the convex condition.

Here some images:

n = 150

convex = True

convex = False

I hope this is useful to someone.