Approximation algorithms for partitioning a rectangle with interior points (Q1263970): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Q4091421 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Triangulating a simple polygon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3962480 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3854665 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3893361 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01840375 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2032846908 / rank | |||
Normal rank |
Latest revision as of 09:56, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation algorithms for partitioning a rectangle with interior points |
scientific article |
Statements
Approximation algorithms for partitioning a rectangle with interior points (English)
0 references
1990
0 references
The article addresses the problem of partitioning a rectilinear polygon into rectangles by introducing a set of line segments (edges) of least total length. Several variations of this problem were shown to be NP- hard, but the computational complexity of some related problems remains unknown. Particularly, the authors present an efficient approximation algorithm for the case where a set of points inside rectilinear polygon is also given and a valid partition must not contain points from this set. The solutions generated by the algorithm are guaranteed to be within three times the optimal solution value. The method used is transformation of a given instance into an instance of another variation of the problem, which we know to solve in polynomial time. It is shown that this approach guarantees abovementioned bounds of approximation.
0 references
approximation algorithms
0 references
partition of rectilinear polygons
0 references
polynomial time complexity
0 references