Computing Optimal DiameterBounded Polygon Partitions.
The minimum asmall partition problem is the problem of partitioning a given simple polygon subpolygons, each with diameter at most a, for a given a > 0. This paper considers the version of problem that disallows Steiner points. This problem is motivated by applications in mesh generations and collision detection. The main result in the paper is a polynomial time algorithm that solves this problem, and either returns an optimal partition or reports the nonexistence of such a partition. This result contrasts with the recent NPcompleteness result for the minimum asmall partition problems for polygons with holes (C. Worman, 15th Canadian Conference on Computational Geometry, 2003). Even though the running time of our algorithm is a polynomial in the input size, it is prohibitive for most real applications and we seek faster algorithms that approximate an optimal solution. We first present a faster 2approximation algorithm for the problem for simple polygons and then a near lineartime algorithm for convex polygons that produces, for any e > 0, an (a+e)small partition with no more polygons than in an optimal asmall partition. We also present an exact polynomial time algorithm for the minimum asmall partition problem with the additional constraint that each piece in partition be convex.
Main Author:  Damian, Mirela. 

Other Authors:  Pemmaraju, Sriram V. 
Language:  English 
Published: 
2004

Online Access: 
http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175647 