Minimal triangulation of a polygon (Problems from MO category P, part 50)
Abstract
With today's 50th anniversary part, we conclude the long-lasting series of articles in which we have gradually introduced you to selected competition problems from the Mathematical Olympiad of category P (programming). These 50 articles have been published on the pages of our magazine from 2000 to the present day, i.e. for a full 25 years. This time, we will show one classical combinatorial problem given in the national round of the 39th MO category P in the school year 1989/90. It deals with the so-called triangulation of a polygon, which means dividing its area into triangles by diagonals that do not cross each other anywhere. As we will see, an efficient solution to this problem will be based on the idea of dynamic programming, a method very often used not only in various competition problems but also in programming in general.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 MATHEMATICS–PHYSICS–INFORMATICS
This work is licensed under a Creative Commons Attribution 4.0 International License.
Autoři, kteří publikují v tomto časopise, souhlasí s následujícími body:
- Autoři si ponechávají copyright a garantují časopisu právo prvního publikování, přitom je práce zároveň licencována pod Creative Commons Attribution licencí, která umožňuje ostatním sdílet tuto práci s tím, že přiznají jejího autora a první publikování v tomto časopisu.
- Autoři mohou vstupovat do dalších samostatných smluvních dohod pro neexkluzivní šíření práce ve verzi, ve které byla publikována v časopise (například publikovat ji v knize), avšak s tím, že přiznají její první publikování v tomto časopisu.
Obsah časopisu podléhá licenci Creative Commons Uveďte autora 3.0 Česko
