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
Zeitschrift:
Top

ISSN: 1863-8279,  1134-5764

Datum der Publikation: 2008

Ausgabe: 16

Nummer: 2

Seiten: 367-387

Art: Artikel

DOI: 10.1007/S11750-008-0055-2 DIALNET GOOGLE SCHOLAR lock_openOpen Access editor

Andere Publikationen in: Top

Zusammenfassung

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