Covering oriented points in the plane with orthogonal polygons is NP-complete.
Cem EvrendilekBurkay GençBrahim HnichPublished in: Electron. Notes Discret. Math. (2010)
Keyphrases
- np complete
- convex hull
- orthogonal projection
- simple polygon
- euclidean geometry
- pspace complete
- satisfiability problem
- np hard
- computational complexity
- grid points
- point sets
- transformation matrix
- data points
- three dimensional
- scale factor
- feature points
- endpoints
- data complexity
- normal vectors
- vanishing points
- polynomial time complexity
- parametric curves
- single point
- conjunctive queries
- image sequences