Open Problems

1. We proved (4/3/97) the existence of triangulations of any polygon or straight line graph, and of convex quadrilateralizations of any orthogonal polygon. What about curved objects? Do spline-polygons have spline-triangulations? An example formed by connecting four quarter-ellipses shows Steiner points may be needed, even for quadratic splines, but maybe they only need to be added in the interior of the splinegon.

2. On 4/8/97 we went over dynamic programming techniques for optimal triangulation (e.g. minimum total edge length) of simple polygons, in O(n³) time or O(E^3/2) if the visibility graph has E edges. So the slowest case is seemingly the most simple, when the polygon is convex. Can we find the minimum length triangulation of convex polygons in o(n³) time? Steve S. suggested Frances Yao's generalization of Knuth's speedup to optimal binary search tree construction (which has the same general dynamic programming form) but it doesn't seem to work.

3. The same dynamic programming methods also work for optimal quadrilateralization, in time O(n⁴). There is sometimes a possible speedup: we can break quadrilaterals into pairs of triangles and reduce the time to O(n³), but only for those quality functions which can be computed by adding separately the qualities of the two triangles (e.g. total edge length, allowing concave quadrilaterals). The speedup doesn't seem to work when we want to use angle-based quality measures, e.g. even as simple a problem as testing whether there exists a partition of a simple polygon into convex quadrilaterals. Can we test for the existence of such a partition in time o(n^4)? What about convex quadrilateralization of non-simple polygons?

4. Non-simple polygons with h holes can be reduced to simple ones by choosing h edges, one going leftwards from the leftmost vertex of each hole boundary. In this way we can find optimal triangulations of them in time O(n^3+h). It is a famous open problem whether minimum length triangulation is polynomial time (so that we can get rid of the exponent of h). Also, can we use e.g. separator-based divide and conquer to reduce the time bound to n^{O(sqrt h)}? If so, can the constants be made small enough for this to actually be more practical than the O(n^3+h) bound?

5. O'Rourke's art gallery book mentions an O(n⁷ log n) time bound for a dynamic programming-based method for partitioning simple polygons into the minimum number of star-shaped regions. Can this be improved? What about dynamic programming for partitioning into the minimum number of convex pieces, presumably this works but is it O(n³), O(n⁴), or worse?

   [Note added later: Jeff Erickson tells me the best known bound for convex partition is O(r²n log n) where r is the number of reflex vertices, which might be as large as n. We haven't gotten to Steiner problems yet but the minimum Steiner partition into convex pieces can also be solved in time O(n + r³) by an algorithm of Chazelle.]

6. Can we find the triangulation of a planar straight line graph (PSLG) that minimizes the maximum edge length in polynomial time? Edelsbrunner and Tan [FOCS '91] solved this for point sets. Extending their results to PSLGs would also solve the problem they left open of minimizing the lexicographically-ordered vector of edge lengths (at least for point sets in general position).

7. A much more famous optimal triangulation problem: can we find the triangulation minimizing the sum of edge lengths in polynomial time? There has been a lot of work on this for point sets, but less for PSLGs, so perhaps the extra complexity of a PSLG would make it easier for an NP-completeness proof to go through.

8. If we are given a set of three-dimensional points, can we find a continuous piecewise linear interpolating function (i.e. a surface formed by projecting the points onto the xy-plane, triangulating, and lifting the triangles back up into 3D) that minimizes the total surface area, in polynomial time? What about a function that maximizes the minimum dihedral angle? Note that examples based on a regular octahedron (oriented with two faces parallel to the xy-plane, so its vertices project to a regular hexagon) show that edge insertion does not work for these problems.

9. What if anything can we prove about optimal quadrilateralization of point sets and/or planar straight line graphs?

10. Does every point set, polygon, or planar straight line graph have a well-defined minimum weight Steiner triangulation? (The minimum weight itself is well defined, but the other possibility is that adding more and more Steiner points might be needed to get closer and closer to some limiting weight.)

11. We showed (4/22/97) that the number of elements required for no-small-angle triangulation could be bounded above and below by integral(1/(local feature size)²), and used this to prove the optimality of quadtree triangulation and Ruppert's incremental Delaunay method. In my paper "Approximating the minimum weight Steiner triangulation" I showed that quadtree triangulation also approximately minimizes the total edge length among all Steiner triangulations of a point set, but left open the problem of extending this result to polygons. For quadtree triangulations, the total edge length is proportional to integral(1/(local feature size)). Is this a general lower bound on the length of all triangulations? If so this would simplify my results and lead to the polygon extension. It would also be of interest to find a polynomial-time approximation to minimum edge length (quadtrees may be nonpolynomial), but perhaps this could be done with the same shortcutting technique used in my paper.

12. Another open question from the same approximate minimum weight paper: there exist convex polygons for which the min weight triangulation requires Steiner points on the boundary. But are Steiner points ever required in the interior of the polygon? If not, one might be able to compute the optimal triangulation by dynamic programming, interesting since no optimal Steiner triangulation result is currently known.

13. We went over the circle-packing method of Bern, Mitchell, and Ruppert (4/24/97), which nonobtusely triangulates any polygon without cracks, using only O(n) triangles. But it produces lots of right triangles. Can it be modified to produce only acute triangles?

14. Bern, Mitchell, and Ruppert's method works by dividing the polygon into kite-shaped regions which are then split into two or four right triangles each. Can we say anything about the quality of the quadrilateral mesh obtained by not splitting the kites?

15. Sometimes, it may be possible to pack more circles into the region bounded by four tangent circles, in such a way that all remaining regions are bounded by only three circles. In general position, however, this doesn't happen. How easily can we tell whether the circles are in a special position that allows this kind of packing?

16. Is there a polynomial time algorithm for nonobtusely triangulating polygons with cracks, or arbitrary planar straight line graphs? There is a lower bound of Omega(n²) on the required output complexity. The only known upper bound is O(n⁴), on the very special case in which the PSLG is itself a triangulation of a simple polygon ("Polynomial size non-obtuse triangulation of polygons").

17. Edelsbrunner and Tan gave an O(n³) algorithm for conforming Delaunay triangulation, a relaxation of nonobtuse triangulation to which the same Omega(n²) lower bound applies. Can the problem be solved in O(n²) complexity?

18. How many tetrahedra or simplices are needed to triangulate a given polyhedron or polytope? This is also closely related to the problem of computing the number of flips required to convert one planar triangulation into another. The worst-case version of the question in 3d (what is the maximum number of tetrahedra required, as a function of n) was answered by Sleator, Tarjan, and Thurston. The algorithmic question (how many are required for this particular polyhedron) remains open. Also open: how many simplices are required to triangulate a d-dimensional hypercube, as a function of d. Do Steiner points ever help reduce the number of tetrahedra or simplices?

19. Is it always possible to tetrahedralize (without Steiner points) the shape formed by forming a convex-polyhedron void inside the kernel of a star-shaped polyhedron?

20. For any point set in R³, one can form a flip graph of the different tetrahedralizations of the point set (partitions of its convex hull into tetrahedra meeting face to face and having the points as vertices), in which two tetrahedralizations are connected by an edge if they differ by a flip (if two face-to-face tetrahedra together form a convex 5-vertex polyhedron, replace them by a three-tetrahedron subdivision of the same polyhedron or vice versa). This graph is bipartite. Can it be disconnected? Or worse, can it have isolated vertices (tetrahedralizations in which no flips are possible)?

21. Does every line through a 3-dimensional Delaunay triangulation intersect at most O(n) tetrahedra?

    [Note added October 1999: Jonathan Shewchuk has found a 3d DT in which a line can stab Omega(n²) tetrahedra.]

22. Can we efficiently construct the triangulation of a 3d point set maximizing the minimum solid angle? (Note that unlike its planar analog, this is not optimized by the Delaunay triangulation, due to the fact that, if three of four vertices of a tetrahedron are fixed, and the solid angle at the fourth point is also fixed, the locus of possible locations for that point is non-spherical. I can prove that this locus is convex, but the proof is messy and algebraic -- is there a simple conceptual proof?)

23. If we are given n points in space, the Delaunay triangulation of which has t tetrahedra, how quickly can we find that triangulation? Chan, Snoeyink and Yap have an algorithm with running time O((n + t) log² t), but this does not quite match the known lower bound of Omega(n log t + t).

    Some more practical problems from Mac (meaning, a solution would likely involve an actual working system, although one might imagine theoretical results in these areas):

    1. Hex meshing with quality approaching that which is producable by hand - i.e., by region decomposition controlled by an expert.
    2. Intelligent meshing of features (if you tell the CAD system to put a certain type of feature on your object, that information should be used by the mesher).
    3. Fast remeshing after a local change.
    4. Mesh smoothing for high order elements with curved boundaries.
    5. Problem dependent, black box meshing, in which the whole process of selecting a mesh type, performing mesh generation, applying a numerical algorithm, etc is automatically performed given some specification of the problem to be solved.
    6. Decomposition into "nice" 2-1/2D regions (generalized cylinders, meeting parallel to each other; one could then apply a planar mesh algorithm to the cylinder cross-section and cut horizontally to get a good 3D mesh).

    ---

    David Eppstein, Theory Group, Dept. Information & Computer Science, UC Irvine.
    Last update: