A practical algorithm for decomposing polygonal domains into convex polygons by diagonals

• José Fernández ^[1] ; Boglárka Tóth ^[2] ; Lázaro Cánovas ^[1] ; Blas Pelegrín ^[1]
  1. [1] Universidad de Murcia

     Universidad de Murcia

     Murcia, España

     
  2. [2] Budapest University of Technology and Economics

     Budapest University of Technology and Economics

     Hungría

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 16, Nº. 2, 2008, págs. 367-387
• Idioma: inglés
• DOI: 10.1007/s11750-008-0055-2
• Enlaces
  • Texto completo (pdf)
• Resumen

  • We present algorithms for decomposing a polygon (with holes) into convex polygons by diagonals. The methods are computationally quick, and although the partitions that they produce may not have minimal cardinality they usually have a low number of convex pieces. Thus, the methods are suitable for being used when achieving a modest load on the CPU time is more important than finding optimal decompositions as, for instance, in location problems.