Covering and packing of triangles intersecting a straight line

We study four geometric optimization problems: , , , and with (a triangle is a right-triangle whose base is parallel to the -axis, perpendicular is parallel to the -axis, and the slope of the hypotenuse is ). The input triangles are constrained to be intersecting a . The straight line can either be a or an line (a line whose slope is ). A right-triangle is said to be a , if the length of both its base and perpendicular is . For 1-right-triangles where the triangles intersect an inclined line, we prove that the set cover and hitting set problems are -hard, whereas the piercing set and independent set problems are in . The same results hold for 1-right-triangles where the triangles are intersecting a horizontal line instead of an inclined line. We prove that the piercing set and independent set problems with right-triangles intersecting an inclined line are -hard. Finally, we give an time exact algorithm for the independent set problem with -right-triangles intersecting a straight line such that takes more than one value from , for some integer . We also present -time dynamic programming algorithms for the independent set problem with 1-right-triangles where the triangles intersect a horizontal line and an inclined line.