Orthogonally convex covering of orthogonal polygons without holes (Q1825650): Difference between revisions

The problem of finding minimal covers of indicated type proves to be difficult. The paper presents methods of obtaining \(O(n^ 2)\)-time minimal cover algorithms for several subclasses of orthogonal polygons which are proved to be time-optimal (the output size may reach \(Cn^ 2)\). It is also shown that the corresponding minimal cover counting problem for these polygon classes may be solved in linear time.