In geometry, a partition of a polygon is a set of primitive units (e.g., triangles, rectangles, etc.), which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length (sum of the perimeters). Polygon partitioning is an important class of problems in computational geometry. There are many different polygon partition problems, depending on the type of polygon being partitioned and on the types of units allowed in the partition. The term "polygon decomposition" is often used as a general term that includes both polygon partitioning and polygon covering, which allows overlapping units.
Applications Polygon decomposition is applied in several areas:
Pattern recognition techniques extract information from an object in order to describe, identify or classify it. An established strategy for recognising a general polygonal object is to decompose it into simpler components, then identify the components and their interrelationships and use this information to determine the shape of the object. In VLSI artwork data processing, layouts are represented as polygons, and one approach to preparation for electron-beam lithography is to decompose these polygon regions into fundamental figures. Polygon decomposition is also used in the process of dividing the routing region into channels. In computational geometry, algorithms for problems on general polygons are often more complex than those for restricted types of polygons such as convex or star-shaped. The point-in-polygon problem is one example. A strategy for solving some of these types of problems on general polygons is to decompose the polygon into simple component parts, solve the problem on each component using a specialized algorithm, and then combine the partial solutions. Other applications include data compression, database systems, image processing and computer graphics.
Partitioning a polygon into triangles
The most well-studied polygon partition problem is partitioning to a smallest number of triangles, also called triangulation. For a hole-free polygon with n {\displaystyle n} vertices, a triangulation can be calculated in time Θ ( n ) {\displaystyle \Theta (n)} . For a polygon with holes, there is a lower bound of Ω ( n log n ) {\displaystyle \Omega (n\log n)} . A related problem is partitioning to triangles with a minimal total edge length, also called minimum-weight triangulation.
Partitioning a polygon into pseudo-triangles
The same two variants of the problem were studied for the case in which the pieces should be pseudotriangles – polygons that like triangles have exactly three convex vertices. The variants are: partitioning to a smallest number of pseudotriangles, and partitioning to pseudotriangles with a minimal total edge length.
Partitioning a rectilinear polygon into rectangles An important sub-family of polygon partition problems arises when the large polygon is a rectilinear polygon, and the goal is to partition it into rectangles. Such partitions are known as rectangular partitions. They have practical applications in a variety of fields, including VLSI design and image processing.
Minimizing the number of components Several polynomial-time algorithms are known to compute a rectangular partition which minimizes the number of component rectangles. See and for surveys. The problem of partitioning a rectilinear polygon into a smallest number of squares (instead of arbitrary rectangles) is NP-hard.
Minimizing the total edge length In some applications, it is more important to minimize the total length of the cuts (e.g. to minimize the cost of performing the partition, or to minimize the amount of dust). This problem is called minimum edge-length rectangular partitioning. It was first studied by Lingas, Pinter, Rivest and Shamir in 1982. The run-time complexity of this problem crucially depends on whether the raw polygon is allowed to have holes. If the raw polygon is hole-free, then an optimal partition can be found in time O ( n 4 ) {\displaystyle O(n^{4})} , where n is the number of vertices of the polygon. In the special case of a "histogram polygon", the complexity improves to O ( n 3 ) {\displaystyle O(n^{3})} . The algorithm uses dynamic programming and relies on the following fact: if the polygon is hole-free, then it has a minimum-length partition in which each maximal line-segment contains a vertex of the boundary. The reason is that, in any minimum-length partition, every maximal line-segment can be "pushed" until it hits one of the vertices of the boundary, without changing the total length. Therefore, there are only O ( n 2 ) {\displaystyle O(n^{2})} candidates for a line segment in an optimal partition, and they can be checked efficiently using dynamic programming. If the raw polygon might have holes, even if they are degenerate holes (i.e., single points), the problem is NP-hard. This can be proved by reduction from Planar SAT. For the case in which all holes are single points, several constant-factor approximations have been developed:
… excerpt ends here. Continue reading the full article.
