Computing Optimal Diameter-Bounded Polygon Partitions.

The minimum a-small 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 non-existence of such a partition. This result contrasts with the recent NP-completeness result for the minimum a-small 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 2-approximation algorithm for the problem for simple polygons and then a near linear-time algorithm for convex polygons that produces, for any e > 0, an (a+e)-small partition with no more polygons than in an optimal a-small partition. We also present an exact polynomial time algorithm for the minimum a-small 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