A quasi-polynomial time approximation scheme for minimum weight triangulation

The MINIMUM WEIGHT TRIANGULATION problem is to find a triangulation T* of minimum length for a given set of points P in the Euclidean plane. It was one of the few longstanding open problems from the famous list of twelve problems with unknown complexity status, published by Garey and Johnson [8] in 1979. Very recently the problem was shown to be NP-hard by Mulzer and Rote. In this paper, we present a quasi-polynomial time approximation scheme for MINIMUM WEIGHT TRIANGULATION.

Authors

• Jan Remy
• Angelika Steger

Keywords

• approximation algorithms
• minimum weight triangulation