The Greedy and Delauney Triangulations are not Bad in the Average Case and Minimum Weight Geometric Triangulation of Multi-Connected Polygons is NP-Complete.

Andrzej Lingas

Browse the full FCT paper archive.