Some NP-hard polygon decomposition problems

DOI10.1109/TIT.1983.1056648MaRDI QIDQ3967065zbMATH OpenOpenAlexWikidataFDO

Authors Joseph O'Rourke, Kenneth J. Supowit

Publication date 1983

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.1983.1056648

zbMATH Keywords

computational geometrysyntactic pattern recognitioncomputational complexity of polygon decomposition

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cited in

(43)

• On colourability of polygon visibility graphs
• Linear-time 3-approximation algorithm for the \(r\)-star covering problem
• A set covering based approach to find the reduct of variable precision rough set
• Modeling dynamics of opinion formation in small groups: a framework capturing individual opinion adjustments
• Improved approximation for guarding simple galleries from the perimeter
• Complexities of efficient solutions of rectilinear polygon cover problems
• Orthogonally convex covering of orthogonal polygons without holes
• Note on covering monotone orthogonal polygons with star-shaped polygons
• Guarding polyominoes under k-hop visibility
• Close approximations of minimum rectangular coverings (extended abstract)
• A constant-factor approximation algorithm for vertex guarding a WV-polygon
• Approximation algorithms for art gallery problems in polygons
• Reflective guarding a gallery
• On gallery watchmen in grids
• Approximability of guarding weak visibility polygons
• Arc fibrations of planar domains
• Rectangularization of digital objects and its relation with straight skeletons
• Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem
• Representing planar domains by polar parameterizations with parabolic parameter lines
• Visibility extension via reflection
• On the difficulty of triangulating three-dimensional nonconvex polyhedra
• Minimum convex partition of a polygon with holes by cuts in given directions
• A linear-time heuristic for minimum rectangular coverings (Extended abstract)
• An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
• On colourability of polygon visibility graphs
• The parameterized complexity of guarding almost convex polygons
• On guarding the vertices of rectilinear domains
• Minimum star partitions of simple polygons in polynomial time
• Polygon guarding with orientation
• Graph problems arising from parameter identification of discrete dynamical systems
• Minimum k-partitioning of rectilinear polygons
• A nearly optimal sensor placement algorithm for boundary coverage
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Guarding galleries and terrains
• Polygon Area Decomposition for Multiple-Robot Workspace Division
• Covering grids and orthogonal polygons with periscope guards
• GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST
• A decision procedure for optimal polyhedron partitioning
• Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
• Rectangular partition is polynomial in two dimensions but NP-complete in three
• On covering orthogonal polygons with star-shaped polygons
• Guarding polyominoes under \(k\)-hop visibility

This page was built for publication: Some NP-hard polygon decomposition problems

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