Research Projects: Splinegons

Computational geometry has largely concentrated on algorithms for straight-sided objects such as polygons or polyhedra rather than on curvy objects. However real life is always going to throw us curves.

A natural definition of a curved planar object is the splinegon, a polygon bounded by algebraic curves, which can either be defined parametrically (x and y being polynomial functions of a parameter t) or implicitly as the solution to a polynomial equation in x and y. Every parametric curve can be represented implicitly but not vice versa; which form one uses depends on where the problem comes from. An important measure of the complexity of these curves is the degree of the associated polynomials.

Anyway, the most basic data structure for straight-sided polygons is a triangulation, a partition of the polygon into three-sided regions using the same vertices as the original polygon. Many other geometric algorithms are based on the existence of a triangulation. What similar thing should we use for splinegons?

Obviously we can define triangulations in exactly the same way. Unfortunately, to triangulate splinegons we may need to increase the degree. Any diagonal in the following splinegon quadrilateral, formed from four arcs of an ellipse, has degree at least three.

More generally, examples like this show that the degree of a diagonal may be up to double the degree of the splinegon edges. However, we don't know whether it is always possible to triangulate splinegons, even with high-degree diagonals.

In the same four-cusp example, we can use four circular arcs instead of a cubic spline diagonal, if we introduce an extra Steiner point in the middle of the splinegon.

Is it always possible to triangulate splinegons, using diagonals of degree matching the splinegon sides, and only introducting Steiner points in the splinegon interior? If so how many Steiner points are needed?