scientific article; zbMATH DE number 4062595

zbMATH Open0651.68060MaRDI QIDQ3796752FDOQ3796752

Authors: David Avis, David Rappaport 

Publication date: 1988

Title of this publication is not available (Why is that?)

Recommendations

• Computing simple circuits from a set of line segments
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Reconstruction of weakly simple polygons from their edges
• Circumscribing polygons and polygonizations for disjoint line segments
• Computing nonsimple polygons of minimum perimeter

zbMATH Keywords

dynamic programmingcomputational geometryNP-completepolynomial algorithmstravelling salesman problemmonotone simple circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Cited In (8)

• Evaluating Monotone Circuits on Cylinders, Planes and Tori
• Any monotone function is realized by interlocked polygons
• Monotone circuits for matching require linear depth
• Computing simple circuits from a set of line segments
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Covering a Simple Polygon by Monotone Directions
• Monotone Pieces of Chains
• Computing Simple Circuits from a Set of Line Segments is NP-Complete

This page was built for publication:

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