Convex Cover and Hidden Set in Funnel Polygons

05/17/2023
by   Reilly Browne, et al.
0

We present linear-time algorithms for both maximum hidden set and minimum convex cover in funnel polygons. These algorithms show that funnel polygons are "homestead" polygons, i.e. polygons for which the hidden set number and the convex cover number coincide. We extend the algorithm to apply to maximum hidden vertex set and use the result to give a 2-approximation for all three problems in pseudotriangles.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset