MINIMUM CONVEX PARTITION OF A POLYGON WITH HOLES BY CUTS IN GIVEN DIRECTIONS

Authors
LINGAS A SOLTAN V
Citation
A. Lingas et V. Soltan, MINIMUM CONVEX PARTITION OF A POLYGON WITH HOLES BY CUTS IN GIVEN DIRECTIONS, theory of computing systems, 31(5), 1998, pp. 507-538
Citations number
28
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
theory of computing systems → ACNP
Volume
31
Issue
5
Year of publication
1998
Pages
507 - 538
Database
ISI
SICI code
Abstract
Let F be a given family of directions in the plane, The problem of par titioning a planar polygon P with holes into a. minimum number of conv ex polygons by cuts in the directions of F is proved to be NP-hard if /F/ greater than or equal to 3 and it is shown to admit a polynomial-t ime algorithm if /F/ less than or equal to 2.