Algorithms for minimum length partitions of polygons (Q1102107): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q62037529 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Multi-Way Search Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Alphabetic Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal Triangulations of Polygonal Domains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Visibility of a simple polygon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The greedy and Delaunay triangulations are not bad in the average case / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 17:04, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for minimum length partitions of polygons |
scientific article |
Statements
Algorithms for minimum length partitions of polygons (English)
0 references
1987
0 references
We show that it is possible to find a diagonal partition of any n-vertex simple polygon into smaller polygons, each of at most m edges, minimizing the total length of the partitioning diagonals, in time \(O(n^ 3 m^ 2)\). We derive the same asymptotic upper time-bound for minimum length diagonal partitions of simple polygons into exactly m-gons provided that the input polgyon can be partitioned into m-gons. Also, in the latter case, if the input polygon is convex, we can reduce the upper time-bound to \(O(n^ 3 \log m)\).
0 references
geometric partition
0 references
computational complexity
0 references
VLSI
0 references
simple polygon
0 references