Triangulations (tilings) and certain block triangular matrices

Abstract

For a convex polygon P with n sides, a 'partitioning' of P into n-2 nonoverlapping triangles each of whose vertices is a vertex of P is called a triangulation or tiling, and each triangle is a tile. Each tile has a given cost associated with it which may differ one from another. This paper considers the problem of finding a tiling of P such that the sum of the costs of the tiles used is a minimum, and explores the curiosity that (an abstract formulation of) it can be cast as a linear program. Further the special structure of the linear program permits a recursive O(n3) algorithm. © 1985 The Mathematical Programming Society, Inc.