O'Rourke Original NP-Hardness Result
- Poses problem/Introduces Steiner points
- Canonical Reduction from 3-SAT
Original NP-Hardness Result for Polygons Without Holes
Extra Hardness of Convex Cover
- Not verifiable, uber hard!
Poly-time Approximation Algorithm
- Uses configurations on a pairwise grid between vertices
- Makes grid finer by redefining a grid among pairwise points between the original grid, etc
- Bounds number of configurations, thereby bounding the number of possible interior convex polygons to try
Near Linear Cover of Disjoint Polygons
- Given disjoint polygons, there exists a unique convexification which has total minimum area and covers all polygons
- Could use this simple technique to piece together remaining disjoint polygons after taking away large convex polygons initially