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

  1. José Fernández 1
  2. Boglárka Tóth 2
  3. Lázaro Cánovas 1
  4. Blas Pelegrín 1
  1. 1 Universidad de Murcia, España
  2. 2 Budapest University of Technology and Economics, Hungría
Revista:
Top

ISSN: 1863-8279,  1134-5764

Año de publicación: 2008

Volumen: 16

Número: 2

Páginas: 367-387

Tipo: Artículo

DOI: 10.1007/S11750-008-0055-2 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Top

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.

Fuente de los datos: Dialnet