Triangulations (tilings) and certain block triangular matrices

For a convex polygonP withn sides, a ‘partitioning’ ofP inton−2 nonoverlapping triangles each of whose vertices is a vertex ofP 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 ofP 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(n ³) algorithm. Research and reproduction of this report were partially supported by the National Science Foundation Grants MCS-8119774, MCS-7926009 and ECS-8012974; Department of Energy Contract DE-AM03-76SF00326, PA# DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and donot necessarily reflect the views of the above sponsors.