Triangulations (tilings) and certain block triangular matrices

From MaRDI portal





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(n^ 3)\) algorithm.











This page was built for publication: Triangulations (tilings) and certain block triangular matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3688133)