An algorithm for determining an opaque minimal forest of a convex polygon (Q1107998)
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: An algorithm for determining an opaque minimal forest of a convex polygon |
scientific article; zbMATH DE number 4066324
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An algorithm for determining an opaque minimal forest of a convex polygon |
scientific article; zbMATH DE number 4066324 |
Statements
An algorithm for determining an opaque minimal forest of a convex polygon (English)
0 references
1987
0 references
Let P be a convex polygon with n vertices in the Euclidean plane. An `opaque forest' for P, denoted F(P), is a finite set of line segments inside or on P so that every line intersecting P also intersects at least one member of F(P). We give an algorithm which computes an opaque minimal (in the \(L_ 2\) sense) forest, \(F^*(P)\), in \(O(n^ 6)\) time using \(O(n^ 2)\) space.
0 references
triangulation
0 references
Steiner tree
0 references
minimum spanning tree
0 references
computational geometry
0 references
convex polygon
0 references
opaque forest
0 references
