Polygon partition

Last updated

In geometry, a partition of a polygon is a set of primitive units (e.g. squares), 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.

Contents

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 covering and partitioning. [1]

Applications

Polygon decomposition is applied in several areas: [1]

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 vertices, a triangulation can be calculated in time . For a polygon with holes, there is a lower bound of .

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 pseodutriangles, and partitioning to pseudotriangles with a minimal total edge length.

Partitioning a rectilinear polygon into rectangles

A special sub-family of polygon partition problems arises when the large polygon is a rectilinear polygon (also called: orthogonal polygon). In this case, the most important component shape to consider is the rectangle. [1]

Rectangular partitions have many applications. In VLSI design, it is necessary to decompose masks into the simpler shapes available in lithographic pattern generators, and similar mask decomposition problems also arise in DNA microarray design. Rectangular partitions can simplify convolution operations in image processing and can be used to compress bitmap images. Closely related matrix decomposition problems have been applied to radiation therapy planning, and rectangular partitions have also been used to design robot self-assembly sequences. [2]

Minimizing the number of components

The problem of minimizing the number of component rectangles is polynomial: several polynomial-time algorithms are known. See [1] :10–13 and [2] :3–5 for surveys.

The problem of partitioning a rectilinear polygon to a smallest number of squares (in contrast to arbitrary rectangles) is NP-hard. [3]

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. [4] [5] 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 , where n is the number of vertices of the polygon. In the special case of a "histogram polygon", the complexity improves to . [4] 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 candidates for a line segment in an optimal partition, and they can be checked efficiently using dynamic programming. [5] :166–167

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. [4] [6] For the case in which all holes are single points, several constant-factor approximations have been developed:

Minimizing the number of blanks

In this setting, the large polygon already contains some pairwise-disjoint rectangles. The goal is to find a partition of the polygon into rectangles such that each original rectangle is contained in one of the pieces, and subject to this, the number of "blanks" (pieces that do not contain an original rectangle) is as small as possible. The following results are known: [12]

Partition a polygon into trapezoids

In VLSI artwork processing systems, it is often required to partition a polygonal region into the minimum number of trapezoids, with two horizontal sides. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. For a hole-free polygon with sides, a smallest such partition can be found in time . [13]

If the number of trapezoids need not be minimal a trapezoidation can be found in time , as a by-product of a polygon triangulation algorithm. [14]

If the polygon does contain holes, the problem is NP-complete, but a 3-approximation can be found in time . [13]

Partition a polygon into convex quadrilaterals

A quadrilateralization or a quadrangulation is a partition into quadrilaterals.

A recurring characteristic of quadrangulation problems is whether they Steiner point are allowed, i.e., whether the algorithm is allowed to add points which are not vertices of the polygon. Allowing Steiner points may enable smaller divisions, but then it is much more difficult to guarantee that the divisions found by an algorithms have minimum size.

There are linear-time algorithms for quadrangulations of hole-free polygons with Steiner points, but they are not guaranteed to find a smallest partition. [15] [16]

Partition a polygon into m-gons

A generalization of previous problems is the partitioning into polygons that have exactly m sides, or at most m sides. Here the goal is to minimize the total edge length. This problem can be solved in time polynomial in n and m. [17] [18]

Partition a polygon into convex polygons

When partitioning a general polygon into convex polygons, several objectives have been studied.

Minimizing the number of components

The optimal convex partitioning problem is to partition a non-convex polygon into as few as possible convex polygons, using only the initial polygon's vertices. There are exact and approximate algorithms for this problem. [19]

Minimizing the number of blanks

The original polygon already contains some pairwise-disjoint convex figures, and the goal is to partition it into convex polygons that such that each original figure is contained in one of the pieces, and subject to this, the number of "blanks" (pieces that do not contain an original figure) is as small as possible. If the large polygon is convex, then in any maximal arrangement of n convex figures, all the holes are convex, and their number is at most , and this is tight. [12]

Equalizing the area and perimeter

The fair polygon partitioning problem [20] is to partition a (convex) polygon into (convex) pieces with an equal perimeter and equal area (this is a special case of fair cake-cutting). Any convex polygon can be easily cut into any number n of convex pieces with an area of exactly 1/n. However, ensuring that the pieces have both equal area and equal perimeter is more challenging. There are algorithms for solving this problem when the number of pieces is a power of 2. [21]

A generalization of this problem is when the area and perimeter measures are replaced with a measure on the body and on the boundary of the polygon, respectively. This problem was studied for 2 and 3 pieces. [22]

There is a further generalization to handle any number of measures.

More general component shapes

More general shapes of pieces have been studied, including: spiral shapes, star polygons and monotone polygons. See [1] for a survey.

See also

Related Research Articles

<span class="mw-page-title-main">Convex hull</span> Smallest convex set containing a given set

In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD).

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

<span class="mw-page-title-main">Euclidean minimum spanning tree</span> Shortest network connecting points

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

<span class="mw-page-title-main">Simple polygon</span> Shape bounded by non-intersecting line segments

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

<span class="mw-page-title-main">Point-set triangulation</span> Simplicial complex in Euclidean geometry

A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

<span class="mw-page-title-main">Guillotine cutting</span> Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine.

<span class="mw-page-title-main">Rectilinear polygon</span> Polygon in which all angles are right

A rectilinear polygon is a polygon all of whose sides meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons.

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner.

<span class="mw-page-title-main">Rotating calipers</span>

In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

<span class="mw-page-title-main">Opaque set</span> Shape that blocks all lines of sight

In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.

In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the flip distance for triangulations of convex polygons.

<span class="mw-page-title-main">Polygonalization</span> Polygon through a set of points

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

<span class="mw-page-title-main">Guillotine partition</span> Process of partitioning a rectilinear polygon

Guillotine partition is the process of partitioning a rectilinear polygon, possibly containing some holes, into rectangles, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing polygon to the opposite edge, similarly to a paper guillotine.

References

  1. 1 2 3 4 5 Mark Keil, J. (2000). "Polygon Decomposition". Handbook of Computational Geometry. pp. 491–518. doi:10.1016/B978-044482537-7/50012-7. ISBN   9780444825377.
  2. 1 2 Eppstein, David (2010). "Graph-Theoretic Solutions to Computational Geometry Problems". Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. Vol. 5911. pp. 1–16. CiteSeerX   10.1.1.249.5965 . doi:10.1007/978-3-642-11409-0_1. ISBN   978-3-642-11408-3. S2CID   16353114.
  3. Realz Slaw. "Tiling an orthogonal polygon with squares". CS stack exchange. Retrieved 19 October 2015.
  4. 1 2 3 Andrzej Lingas and Ron Y Pinter and Ron L Rivest and Adi Shamir (1982). "Minimum edge length partitioning of rectilinear polygons" (PDF). Proc. 20th Allerton Conf. Commun. Control Comput: 53–63.
  5. 1 2 3 Du, Ding-Zhu; Ko, Ker-I.; Hu, Xiaodong (2012). Design and Analysis of Approximation Algorithms. Springer Optimization and Its Applications. New York: Springer-Verlag. pp. 165–209, chapter 5 "guillotine cut". ISBN   978-1-4614-1700-2.
  6. 1 2 Gonzalez, Teofilo; Zheng, Si-Qing (1985-06-01). "Bounds for partitioning rectilinear polygons". Proceedings of the first annual symposium on Computational geometry - SCG '85. Baltimore, Maryland, USA: Association for Computing Machinery. pp. 281–287. doi:10.1145/323233.323269. ISBN   978-0-89791-163-4. S2CID   12588297.
  7. Levcopoulos, C (1986-08-01). "Fast heuristics for minimum length rectangular partitions of polygons". Proceedings of the second annual symposium on Computational geometry - SCG '86. Yorktown Heights, New York, USA: Association for Computing Machinery. pp. 100–108. doi: 10.1145/10515.10526 . ISBN   978-0-89791-194-8. S2CID   16106423.
  8. Gonzalez, Teofilo F.; Razzazi, Mohammadreza; Zheng, Si-Qing (1993-12-01). "An efficient divide-and-conquer approximation algorithm for partitioning into d-boxes". International Journal of Computational Geometry & Applications. 03 (4): 417–428. doi:10.1142/S0218195993000269. ISSN   0218-1959.
  9. Gonzalez, Teofilo; Zheng, Si-Qing (1989-06-01). "Improved bounds for rectangular and guillotine partitions". Journal of Symbolic Computation. 7 (6): 591–610. doi: 10.1016/S0747-7171(89)80042-2 . ISSN   0747-7171.
  10. Arora, S. (October 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". Proceedings of 37th Conference on Foundations of Computer Science. pp. 2–11. doi:10.1109/SFCS.1996.548458. ISBN   0-8186-7594-2. S2CID   1499391.
  11. Mitchell, Joseph S. B. (1999-01-01). "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems". SIAM Journal on Computing. 28 (4): 1298–1309. doi:10.1137/S0097539796309764. ISSN   0097-5397.
  12. 1 2 Akopyan, Arseniy; Segal-Halevi, Erel (2018-01-01). "Counting Blanks in Polygonal Arrangements". SIAM Journal on Discrete Mathematics. 32 (3): 2242–2257. arXiv: 1604.00960 . doi:10.1137/16M110407X. ISSN   0895-4801. S2CID   123397485.
  13. 1 2 Asano, Takao; Asano, Tetsuo; Imai, Hiroshi (1986). "Partitioning a polygonal region into trapezoids". Journal of the ACM. 33 (2): 290. doi:10.1145/5383.5387. hdl: 2433/98478 . S2CID   15296037.
  14. Chazelle, Bernard (2007). "Triangulating a simple polygon in linear time". Discrete & Computational Geometry . 6 (3): 485–524. doi: 10.1007/bf02574703 .
  15. H. Everett; W. Lenhart; M. Overmars; T. Shermer; J. Urrutia. (1992). "Strictly convex quadrilateralizations of polygons". Proc. 4th Canad. Conf. Comput. Geom. pp. 77–83.
  16. Ramaswami, Suneeta; Ramos, Pedro; Toussaint, Godfried (1998). "Converting triangulations to quadrangulations". Computational Geometry . 9 (4): 257. doi: 10.1016/s0925-7721(97)00019-9 .
  17. Lingas, Andrzej; Levcopoulos, Christos; Sack, Jörg (1987). "Algorithms for minimum length partitions of polygons". BIT. 27 (4): 474. doi:10.1007/bf01937272. S2CID   30936524.
  18. Levcopoulos, Christos; Lingas, Andrzej; Sack, Jörg-R. (1989). "Heuristics for optimum binary search trees and minimum weight triangulation problems". Theoretical Computer Science. 66 (2): 181. doi: 10.1016/0304-3975(89)90134-5 .
  19. Hertel, Stefan; Mehlhorn, Kurt (1983). "Fast triangulation of simple polygons". In Karpinski, Marek (ed.). Foundations of Computation Theory. Lecture Notes in Computer Science. Vol. 158. Berlin, Heidelberg: Springer. pp. 207–218. doi:10.1007/3-540-12689-9_105. ISBN   978-3-540-38682-7.
  20. Nandakumar, R.; Rao, N. Ramana (August 2012). "'Fair' Partitions of Polygons - an Introduction". Proceedings - Mathematical Sciences. 122 (3): 459–467. arXiv: 0812.2241 . doi:10.1007/s12044-012-0076-5. ISSN   0253-4142. S2CID   189909962.
  21. Armaselu, Bogdan; Daescu, Ovidiu (2015-11-23). "Algorithms for fair partitioning of convex polygons". Theoretical Computer Science. 607: 351–362. doi: 10.1016/j.tcs.2015.08.003 . ISSN   0304-3975.
  22. Bespamyatnikh, Sergei (2003). "On Partitioning a Cake". In Akiyama, Jin; Kano, Mikio (eds.). Discrete and Computational Geometry: Japanese Conference, JCDCG 2002, Tokyo, Japan, December 6-9, 2002, Revised Papers. Lecture Notes in Computer Science. Vol. 2866. Berlin, Heidelberg: Springer. pp. 60–71. doi:10.1007/978-3-540-44400-8_7. ISBN   978-3-540-44400-8.