I detta dokument introduceras begreppen formbarhet och kastabilitet för enkla polygoner och relaterar formbarhet till monotonitet. Vi specificerar en (n) algoritm för att bestämma alla n framåt maximal monoton kedjor av en enkel polygon och tillämpa denna algoritm på problemen med att bestämma 2-Moldability, 2-Castability och den minsta monoton sönderdelning av en enkel polygon 9]. Våra resultat inkluderar en enkel optimal algoritm som löser det minsta monotona nedbrytningsproblemet, en optimal algoritm för att bestämma 2-Moldability och en O(n log n) algoritm för att bestämma 2-Castability.
REF presenterar en O(n log n) tidsalgoritm (oimplementerad) för 2D-fall där en polygon är 2-kastbar.
Moldable and Castable Polygons
{'venue': 'In Proc. 4th Canad. Conf. Comput. Geom', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}