Some NP-hard polygon decomposition problems
DOI10.1109/TIT.1983.1056648zbMATH Open0501.68036OpenAlexW1981988453WikidataQ56700239 ScholiaQ56700239MaRDI QIDQ3967065FDOQ3967065
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
computational geometrysyntactic pattern recognitioncomputational complexity of polygon decomposition
Pattern recognition, speech recognition (68T10) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Cited In (39)
- 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
- 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
- Close approximations of minimum rectangular coverings (extended abstract)
- A constant-factor approximation algorithm for vertex guarding a WV-polygon
- Reflective guarding a gallery
- Approximation algorithms for art gallery problems in polygons
- Approximability of guarding weak visibility polygons
- On gallery watchmen in grids
- Rectangularization of digital objects and its relation with straight skeletons
- Arc fibrations of planar domains
- Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem
- Representing planar domains by polar parameterizations with parabolic parameter lines
- Minimum convex partition of a polygon with holes by cuts in given directions
- On the difficulty of triangulating three-dimensional nonconvex polyhedra
- 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
- 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
- Guarding polyominoes under \(k\)-hop visibility
- On covering orthogonal polygons with star-shaped polygons
- On colourability of polygon visibility graphs
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)
