DOIAbstract
A minimum k-partition decomposes a rectilinear polygon with n vertices into aminimum number of disjoint rectilinear components with no more than k vertices each (k<n). First, we derive a new lower bound for the number of components in a k-partition. Then we present algorithms to compute minimum k-partitions for two classes of rectilinear polygons. A rectilinear polygon is called x-convex (y-covex) if the intersection of each horizontal (vertical) line with the polygon is either one line segment or empty. It is called degenerate if it has two vertices that can be joint by a horizontal or vertical line segment inside the polygon. Our first partitioning algorithm computes minimum k-partitions for non-degenerate rectilinear polygons that are x-...
Add to ORKG