Orthogonally convex covering of orthogonal polygons without holes (Q1825650)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Orthogonally convex covering of orthogonal polygons without holes |
scientific article; zbMATH DE number 4121428
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Orthogonally convex covering of orthogonal polygons without holes |
scientific article; zbMATH DE number 4121428 |
Statements
Orthogonally convex covering of orthogonal polygons without holes (English)
0 references
1989
0 references
The problem of finding minimal covers of indicated type proves to be difficult. The paper presents methods of obtaining \(O(n^ 2)\)-time minimal cover algorithms for several subclasses of orthogonal polygons which are proved to be time-optimal (the output size may reach \(Cn^ 2)\). It is also shown that the corresponding minimal cover counting problem for these polygon classes may be solved in linear time.
0 references
computational geometry
0 references
orthogonal convexity
0 references
dent diagram
0 references
minimal cover
0 references
orthogonal polygons
0 references
cover counting
0 references
0.93388057
0 references
0.9332429
0 references
0.9239818
0 references
0.8978487
0 references
0.8919959
0 references
0.8867072
0 references
0.8845024
0 references
0.8822126
0 references
