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. |
| Format: | |
| Language: | English |
| Published: |
2004
|
| Online Access: |
http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175647 |