A practical algorithm for decomposing polygonal domains into convex polygons by diagonals |
| |
Authors: | José Fernández Boglárka Tóth Lázaro Cánovas Blas Pelegrín |
| |
Institution: | (1) Department of Statistics and Operations Research, University of Murcia, Murcia, Spain;(2) Department of Differential Equations, Budapest University of Technology and Economics, Budapest, Hungary |
| |
Abstract: | 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.
Part of the results in this paper are from Fernández (1999), and were presented in Fernández et al. (1998). This work has been supported by the Ministry of Science and Technology of Spain under the research projects BEC2002-01026,
SEJ2005-06273/ECON (J. Fernández, B. Tóth and B. Pelegrín) and TIC2003-05982-C05-03 (L. Cánovas), in part financed by the
European Regional Development Fund (ERDF). |
| |
Keywords: | Convex polygon decomposition Polygonal holes Location |
本文献已被 SpringerLink 等数据库收录! |
|