Some NP-hard polygon decomposition problems
From MaRDI portal
Publication:3967065
DOI10.1109/TIT.1983.1056648zbMath0501.68036OpenAlexW1981988453WikidataQ56700239 ScholiaQ56700239MaRDI QIDQ3967065
Kenneth J. Supowit, Joseph O'Rourke
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
computational geometrysyntactic pattern recognitioncomputational complexity of polygon decomposition
Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10) Discrete mathematics in relation to computer science (68R99)
Related Items
Covering grids and orthogonal polygons with periscope guards, Parameterized Analysis of Art Gallery and Terrain Guarding, On gallery watchmen in grids, A linear-time heuristic for minimum rectangular coverings (Extended abstract), Guarding galleries and terrains, Note on covering monotone orthogonal polygons with star-shaped polygons, Polygon guarding with orientation, Reflective guarding a gallery, Rectangularization of digital objects and its relation with straight skeletons, On colourability of polygon visibility graphs, Combinatorics and complexity of guarding polygons with edge and point 2-transmitters, The parameterized complexity of guarding almost convex polygons, Graph problems arising from parameter identification of discrete dynamical systems, Improved approximation for guarding simple galleries from the perimeter, Minimum k-partitioning of rectilinear polygons, Covering orthogonal polygons with star polygons: The perfect graph approach, On the difficulty of triangulating three-dimensional nonconvex polyhedra, A nearly optimal sensor placement algorithm for boundary coverage, Complexities of efficient solutions of rectilinear polygon cover problems, GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST, On covering orthogonal polygons with star-shaped polygons, LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM, On guarding the vertices of rectilinear domains, Approximation algorithms for art gallery problems in polygons, Arc fibrations of planar domains, Representing planar domains by polar parameterizations with parabolic parameter lines, A set covering based approach to find the reduct of variable precision rough set, Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem, On Colourability of Polygon Visibility Graphs, Orthogonally convex covering of orthogonal polygons without holes, A decision procedure for optimal polyhedron partitioning, An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries, Rectangular partition is polynomial in two dimensions but NP-complete in three, Polygon Area Decomposition for Multiple-Robot Workspace Division, A constant-factor approximation algorithm for vertex guarding a WV-polygon, Approximability of guarding weak visibility polygons
