In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, a partition of a
polygon
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
is a set of primitive units (e.g. squares), which do not overlap and whose
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
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.
Polygon partitioning is an important class of problems in
computational geometry
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 ar ...
. 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
In geometry, a covering of a polygon is a set of primitive units (e.g. squares) 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 ...
and partitioning.
Applications
Polygon decomposition is applied in several areas:
[
* ]Pattern recognition
Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphi ...
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
Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) c ...
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
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 ar ...
, 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
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression ...
, database systems
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases span ...
, image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
and computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
.
Partitioning a polygon into triangles
The most well-studied polygon partition problem is partitioning to a smallest number of triangles, also called triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points.
Applications
In surveying
Specifically in surveying, triangulation involves only angle me ...
. 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 pseudotriangle
In Euclidean plane geometry, a pseudotriangle (''pseudo-triangle'') is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (''pseudo-triangulations'') is a partition of a region ...
s – 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
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.
In many cases another definition is pr ...
(also called: orthogonal polygon). In this case, the most important component shape to consider is the rectangle
In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram containi ...
.[
Rectangular partitions have many applications. In ]VLSI
Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) c ...
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
In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
operations in image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
and can be used to compress bitmap image
In computing, a bitmap is a mapping from some domain (for example, a range of integers) to bits. It is also called a bit array or bitmap index.
As a noun, the term "bitmap" is very often used to refer to a particular bitmapping application: th ...
s. Closely related matrix decomposition problems have been applied to radiation therapy
Radiation therapy or radiotherapy, often abbreviated RT, RTx, or XRT, is a therapy using ionizing radiation, generally provided as part of cancer treatment to control or kill malignant cells and normally delivered by a linear accelerator. Radia ...
planning, and rectangular partitions have also been used to design robot self-assembly
Self-assembly is a process in which a disordered system of pre-existing components forms an organized structure or pattern as a consequence of specific, local interactions among the components themselves, without external direction. When the ...
sequences.
Minimizing the number of components
The problem of minimizing the number of component rectangles is polynomial: several polynomial-time algorithms are known. See [ and ][ for surveys.
The problem of partitioning a rectilinear polygon to a smallest number of ''squares'' (in contrast to arbitrary rectangles) is ]NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
.
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 , where ''n'' is the number of vertices of the polygon. In the special case of a "histogram polygon", the complexity improves to . The algorithm uses dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
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.
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
In computer science, the planar 3-satisfiability problem (abbreviated PLANAR 3SAT or PL3SAT) is an extension of the classical Boolean 3-satisfiability problem to a planar incidence graph. In other words, it asks whether the variables of a give ...
. For the case in which all holes are single points, several constant-factor approximations have been developed:
* A (3+sqrt(3)) approximation in time ;
*A (3+sqrt(3)) approximation in time ;
*A 4 approximation in time (more generally, in ''d'' dimensions, it is a approximation in time ),
* A 3 approximation in time ;
* A 1.75 approximation in time (more generally, in ''d'' dimensions, it is a approximation in time ); the latter approximation uses a restricted variant of the problem called guillotine partitioning, in which the cuts must be ''guillotine cuts'' (edge-to-edge cuts).
*Several polynomial-time approximation scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an insta ...
s using sophisticated guillotine cuts.
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:
* If the large polygon is a rectangle, then in any maximal arrangement of ''n'' rectangles, all the holes are rectangles, and their number is at most , and this is tight.
* If the large polygon is a rectilinear polygon with ''T'' reflex vertices, then in any maximal arrangement of ''n'' rectangles, the holes can be partitioned into at most rectangles, and this is tight.
Partition a polygon into trapezoids
In VLSI artwork processing systems, it is often required to partition a polygonal region into the minimum number of trapezoid
A quadrilateral with at least one pair of parallel sides is called a trapezoid () in American and Canadian English. In British and other forms of English, it is called a trapezium ().
A trapezoid is necessarily a Convex polygon, convex quadri ...
s, 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 .[
If the number of trapezoids need not be minimal a trapezoidation can be found in time , as a by-product of a ]polygon triangulation
In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is .
Triangulations may be v ...
algorithm.
If the polygon does contain holes, the problem is NP-complete, but a 3-approximation can be found in time .
Partition a polygon into convex quadrilaterals
A ''quadrilateralization'' or a ''quadrangulation'' is a partition into quadrilateral
In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...
s.
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.
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''.
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 polygon
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...
s, using only the initial polygon's vertices. There are exact and approximate algorithms for this problem.
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.
Equalizing the area and perimeter
The ''fair polygon partitioning'' problem 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
Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
). 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.
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.
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
In mathematics, a spiral is a curve which emanates from a point, moving farther away as it revolves around the point.
Helices
Two major definitions of "spiral" in the American Heritage Dictionary are:[star polygon
In geometry, a star polygon is a type of non-convex polygon. Regular star polygons have been studied in depth; while star polygons in general appear not to have been formally defined, certain notable ones can arise through truncation operations ...]
s and monotone polygon
In geometry, a polygon ''P'' in the plane is called monotone with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects the boundary of ''P'' at most twice.
Similarly, a polygonal chain ''C'' is called monotone with respec ...
s. See for a survey.
See also
* Polygon covering
In geometry, a covering of a polygon is a set of primitive units (e.g. squares) 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 ...
– a related problem in which the pieces are allowed to overlap.
* Packing problem
Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few conta ...
– a related problem in which the pieces have to fit within the entire large object but do not have to cover it entirely.
* Euclidean tilings by convex regular polygons
Euclidean plane tilings by convex regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Kepler in his ''Harmonices Mundi'' (Latin: ''The Harmony of the World'', 1619).
Notation of Eucli ...
– a problem of partitioning the entire plane to simple polygons such as rectangles
In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram containin ...
.
* Squaring the square
Squaring the square is the problem of tiling an integral square using only other integral squares. (An integral square is a square whose sides have integer length.) The name was coined in a humorous analogy with squaring the circle. Squaring the sq ...
– a problem of partitioning an integral square using only other integral squares.
* Space partitioning
In geometry, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). In other words, space partitioning divides a space into non-overlapping regions. Any ...
* Tiling puzzle
Tiling puzzles are puzzles involving two-dimensional packing problems in which a number of flat shapes have to be assembled into a larger given shape without overlaps (and often without gaps). Some tiling puzzles ask you to dissect a given ...
– a puzzle of packing several given pieces into a given larger polygon.
* Guillotine partition
References
{{reflist
Computational geometry
Polygons
Packing problems