Fixed parameter algorithms and other results for convex patitions
Magdalene Grantson Borgelt · 2004
It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NP-hard. Partitioning polygons with holes into the minimum number of convex polygons MNCP is also known to be NP-hard. We show that The MWCP and MNCP problem for general PSLGs where the sum of the hole vertices and re ex vertices inside the convex hull is sub-logarithmic can be solved in polynomial time. In particular we provide algorithms such that: 1. For any convex polygon P with n perimeter vertices and k hole vertices, the MNCP problem can be solved within the following time bounds: { For any constant k, it can be solved in linear time. { For k = O( log n log log n), it can be solved in time polynomial in n. That is O(n k6k5 < 216k) time. 2. For any convex polygon P with n perimeter vertices and k hole vertices, the MWCP problem can be solved within the following time bounds: { For any constant k, it can be solved in O(n3) time. { For k = O( log n log log n) it can be solved in time polynomial in n. That is O(n3 < k4k8 < 213k) time. { For k = 2 it can be solved in O(n2) time. (We apply techniques used to solve the MLCP problem mentioned below.) 3. A special case of the MWCP problem is a polygon with a single hole vertex v. We will refer to this problem as the minimum local convex partition (MLCP) problem. We give a MLCP optimal algorithm solving the problem in linear time if the n edges incident to v are sorted in clockwise order. For unsorted n incident edges, we provide an (n log n) lower time bound. A generalized case is when we need to insert edges of minimum total length in order to remove concavity around one specialized vertex. The minimum weight triangulation(MWT) of an MWCP of a polygon P is at most O(n) longer than its MWT if collinearity of two or more edges is allowed and (log n) if otherwise. We also show some other related results. (Less)