Triangulations (tilings) and certain block triangular matrices
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.
- Regular production systems and triangle tilings
- Dynamic programming and graph optimization problems
- The associahedron and triangulations of the \(n\)-gon
- scientific article; zbMATH DE number 3908501 (Why is no real title available?)
- A reinforcement learning based algorithm to find a triangular Graham partition
- On a linear program for minimum-weight triangulation
- Optimal area polygonisation problems: mixed integer linear programming models
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)