An O(n^ 3) algorithm for finding the minimal opaque forest of a convex polygon

DOI10.1016/0020-0190(88)90122-6MaRDI QIDQ1114398zbMATH OpenOpenAlexFDO

Authors Pratul Dublish

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90122-6

zbMATH Keywords

computational geometryconvex polygonminimal opaque forest

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

An \(O(n^ 6)\) algorithm for computing the minimal opaque forest of a convex polygon has been proposed by \textit{V. Akman} [ibid. 24, 193-198 (1987; Zbl 0653.68030)]. We show that a simple modification improves the running time of this algorithm to \(O(n^ 3)\).

Recommendations

• An algorithm for determining an opaque minimal forest of a convex polygon
• A counterexample to the algorithms for determining opaque minimal forests
• An Optimal Algorithm for Computing Visibility in the Plane
• Opaque sets
• Opaque sets

Cites work

• An algorithm for determining an opaque minimal forest of a convex polygon

Cited in

(7)

• An algorithm for determining an opaque minimal forest of a convex polygon
• A counterexample to the algorithms for determining opaque minimal forests
• Optimization of a subclass of conjunctive queries
• Opaque sets
• Improving the lower bound on opaque sets for equilateral triangle
• Opaque sets
• Computing Opaque Interior Barriers à la Shermer

This page was built for publication: An \(O(n^ 3)\) algorithm for finding the minimal opaque forest of a convex polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114398)