Fixed Parameter Algorithms for Minimum Weight Partitions
Christian Borgelt, Magdalene Grantson, Christos Levcopoulos · 2006
In this paper we propose to solve two hard geometric optimization problems: We describe a fixed parame- ter algorithm for computing the minimum weight tri- angulation (MWT) of a simple polygon with (n k) vertices on the perimeter and k hole vertices in the in- terior, that is, for a total of n vertices. We show that the MWT can be found in time at most O(n 4 4 k k), and thus in time polynomial in n if kO(logn). We implemented our algorithm in Java and report exper- iments backing our analysis. Given a convex polygon with (n k) vertices on the perimeter and k hole vertices in the interior, that is, for a total of n vertices, we also describe a fixed parameter algorithm for computing the mini- mum weight convex partition (MWCP) of the input. We show that the MWCP problem can be found in at most O(n 3 · k 4k 8 · 2 13k ) time, and thus at O(n 3 ) time if k is constant, and in time polynomial in n if k = O( log n log log n ). Our results for the MWCP problem hold also for the more general case where the input is an n-vertex PSLG and k is the total number of holes and/or reflex vertices inside the convex hull.